C++多线程快速排序输出文件出现重复有序段求助

我做课程项目时，要求用C++的thread实现排序算法。通过单独文件生成随机数，用.sh脚本运行快速排序并记录运行时间，但始终出现排序异常：输出文件mysort.out里的元素重复出现有序段，比如先从101到999，然后再次从101到999。推测是合并逻辑问题，但反复检查代码、修改合并方式都没解决，附上代码求帮助。

#include <iostream>
#include <fstream>
#include <thread>
#include <vector>
#include <algorithm>

using namespace std;

const int SIZE = 1000000;
const int THREAD_COUNT = 12;

void QuickSort(int* array, int left, int right) {
  int i = left, j = right;
  int pivot = array[(left + right) / 2];

  while (i <= j) {
    while (array[i] < pivot) i++;
    while (array[j] > pivot) j--;
    if (i <= j) {
      swap(array[i], array[j]);
      i++;
      j--;
    }
  }

  if (left < j) {
    QuickSort(array, left, j);
  }
  if (i < right) {
    QuickSort(array, i, right);
  }
}

void Merge(int* array, int size, const vector<int>& sizes) {
  int* temp = new int[size];
  int index = 0;
  for (int i = 0; i < sizes.size(); i++) {
    copy(array + index, array + index + sizes[i], temp + index);
    index += sizes[i];
  }
  copy(temp, temp + size, array);
  delete[] temp;
}

void SortThread(int* array, int left, int right, vector<int>* sizes) {
  QuickSort(array, left, right);
  sizes->push_back(right - left + 1);
}

int main(int argc, char* argv[]) {
  int array[SIZE];
  int size = 0;
  int num = 0;
  ifstream fin(argv[1]);
  while (fin >> num && size < SIZE) {
    array[size] = num;
    size++;
  }
  fin.close();

  vector<thread> threads;
  vector<int> sizes;

  int chunkSize = size / THREAD_COUNT;
  int left = 0;
  int right = chunkSize - 1;
  for (int i = 0; i < THREAD_COUNT; i++) {
    if (i == THREAD_COUNT - 1) {
      right = size - 1;
    }
    threads.emplace_back(SortThread, array, left, right, &sizes);
    left = right + 1;
    right = left + chunkSize - 1;
  }

  for (int i = 0; i < THREAD_COUNT; i++) {
    threads[i].join();
  }

  Merge(array, size, sizes);

  ofstream fout("mysort.out", ofstream::out);
  if (!fout){
    cerr << "Error" << endl; 
    return 1; 
  }
  for (int i = 0; i < size; i++) {
    fout << array[i] << "\n";
  }
  fout.close();

  return 0;
}

问题原因分析 #

1. 线程安全问题：多个线程同时向sizes向量执行push_back操作，std::vector并非线程安全容器，并发修改会引发数据竞争，导致sizes中的分段长度或顺序被破坏，后续合并逻辑拿到错误的分段信息，最终输出重复有序段。
2. 合并函数无效：当前Merge函数只是将原数组内容复制到临时数组再拷贝回去，完全没有实现归并排序的合并逻辑——即便sizes正确，也只会保留多个独立的有序分段，不会合并成完整的有序数组。

修复方案 #

1. 解决线程安全问题 #

给sizes的访问添加互斥锁，确保push_back操作原子执行：

#include <mutex> // 新增头文件

std::mutex sizes_mutex; // 全局互斥锁

void SortThread(int* array, int left, int right, vector<int>* sizes) {
  QuickSort(array, left, right);
  std::lock_guard<std::mutex> lock(sizes_mutex); // 加锁保护
  sizes->push_back(right - left + 1);
}

2. 实现真正的多路归并逻辑 #

替换原Merge函数，实现多路归并，将多个有序段合并为一个有序数组：

#include <climits> // 新增头文件，用于INT_MAX

void Merge(int* array, int size, const vector<int>& sizes) {
  int* temp = new int[size];
  vector<int> indices(THREAD_COUNT, 0); // 记录每个分段的当前遍历位置
  int current = 0;

  // 计算每个分段的起始索引
  vector<int> segment_starts(THREAD_COUNT, 0);
  for (int i = 1; i < THREAD_COUNT; ++i) {
    segment_starts[i] = segment_starts[i-1] + sizes[i-1];
  }

  while (current < size) {
    int min_val = INT_MAX;
    int min_segment_idx = -1;

    // 遍历所有分段，找到当前最小元素
    for (int i = 0; i < THREAD_COUNT; ++i) {
      if (indices[i] < sizes[i]) {
        int current_val = array[segment_starts[i] + indices[i]];
        if (current_val < min_val) {
          min_val = current_val;
          min_segment_idx = i;
        }
      }
    }

    // 将最小元素放入临时数组
    temp[current++] = min_val;
    indices[min_segment_idx]++;
  }

  // 将排序后的临时数组复制回原数组
  copy(temp, temp + size, array);
  delete[] temp;
}

3. 验证分段划分正确性 #

可以在主线程创建线程前添加日志，确认分段范围连续且无重叠：

// 主线程创建线程前添加
for (int i = 0; i < THREAD_COUNT; i++) {
  if (i == THREAD_COUNT - 1) {
    right = size - 1;
  }
  cout << "Thread " << i << ": 范围[" << left << ", " << right << "]" << endl;
  threads.emplace_back(SortThread, array, left, right, &sizes);
  left = right + 1;
  right = left + chunkSize - 1;
}

内容的提问来源于stack exchange，提问作者Stephen Martinez