多线程归并排序无法正确排序数组的问题排查求助

核心错误原因 #

1. 线程参数生命周期覆盖问题 #

创建线程的循环中，你使用栈上的局部变量SortThreadArgs args传递参数：

SortThreadArgs args = {nums, start, end, result};
pthread_create(&threads[i], NULL, sort_thread, &args);

pthread_create会立即返回，线程可能在循环迭代更新args后才启动，导致多个线程读取到同一个被覆盖的参数值，最终每个线程处理的数组区间完全错误，这是子数组未正确排序的直接原因。

单线程版本用数组merge_sort_args args[thread_count]存储每个线程的参数，每个线程对应独立的数组元素，不存在生命周期覆盖问题，因此单线程运行正常。

2. 多线程排序阶段的数组交叉读写冲突 #

你的merge_sort_aux逻辑会交替将nums和result作为源数组与目标数组递归排序，但多个线程同时操作这两个全局数组的不同区间时，会互相覆盖对方的中间排序结果。例如：

• 线程0排序[0,5]时会修改nums[0..5]和result[0..5]
• 线程1排序[5,10]时会修改nums[5..10]和result[5..10]
  递归过程中merge_sort_aux会交换源和目标数组，导致两个线程的读写操作交叉干扰，破坏了各自的排序中间状态。

3. 最终合并阶段逻辑错误 #

原代码的合并循环逻辑完全不符合归并排序的合并规则：

for (int i = 0; i < thread_count; i++)
{
    int start = i * (count / thread_count);
    int mid = start;
    int end = ...;
    merge(nums, 0, mid, end, result);
}

这段代码每次尝试将[0, mid]与[mid, end]合并，但mid等于当前子数组的起始位置，相当于重复合并前缀与未正确排序的子数组，最终导致数组出现重复元素和乱序。

4. 不必要的全局锁滥用 #

merge函数中添加了全局锁pthread_mutex_lock(&merge_lock)，但多线程排序阶段每个线程的merge操作仅处理自身子区间，不存在共享数据竞争。锁不仅会降低并发效率，还可能在递归排序过程中引发不必要的等待，间接破坏排序状态。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <assert.h>

typedef struct Arguments
{
    long *nums;
    int start;
    int end;
    long *temp; // 每个线程独立的临时数组，避免交叉干扰
} SortThreadArgs;

int thread_count = 2;

void print_long_array(const long *array, int count)
{
    for (int i = 0; i < count; ++i)
    {
        printf("%ld\n", array[i]);
    }
}

// 仅合并指定区间，无全局共享冲突
void merge(long nums[], int from, int mid, int to, long temp[])
{
    int left = from;
    int right = mid;
    int i = from;

    for (; i < to && left < mid && right < to; i++)
    {
        if (nums[left] <= nums[right])
        {
            temp[i] = nums[left];
            left++;
        }
        else
        {
            temp[i] = nums[right];
            right++;
        }
    }
    if (left < mid)
    {
        memcpy(&temp[i], &nums[left], (mid - left) * sizeof(long));
    }
    else if (right < to)
    {
        memcpy(&temp[i], &nums[right], (to - right) * sizeof(long));
    }
    // 将合并结果拷贝回原数组对应区间
    memcpy(&nums[from], &temp[from], (to - from) * sizeof(long));
}

// 排序指定区间，使用线程独立的temp数组
void merge_sort_aux(long nums[], int from, int to, long temp[])
{
    if (to - from <= 1)
    {
        return;
    }

    int mid = (from + to) / 2;
    merge_sort_aux(nums, from, mid, temp);
    merge_sort_aux(nums, mid, to, temp);
    merge(nums, from, mid, to, temp);
}

void *sort_thread(void *arg)
{
    SortThreadArgs *args = (SortThreadArgs *)arg;
    merge_sort_aux(args->nums, args->start, args->end, args->temp);
    // 释放线程独立的临时数组与参数
    free(args->temp);
    free(args);
    pthread_exit(NULL);
}

long *merge_sort(long nums[], int count)
{
    // 拷贝原数组，避免修改输入
    long *result = malloc(count * sizeof(long));
    assert(result != NULL);
    memcpy(result, nums, count * sizeof(long));

    pthread_t threads[thread_count];
    int base_step = count / thread_count;
    int mod = count % thread_count;

    for (int i = 0; i < thread_count; i++)
    {
        int start = i * base_step;
        int end = start + base_step;
        if (i == thread_count - 1)
        {
            end += mod; // 最后一个线程处理剩余元素
        }

        // 为每个线程分配独立的参数和临时数组
        SortThreadArgs *args = malloc(sizeof(SortThreadArgs));
        args->nums = result;
        args->start = start;
        args->end = end;
        args->temp = malloc(count * sizeof(long));

        pthread_create(&threads[i], NULL, sort_thread, args);
    }

    // 等待所有线程完成子数组排序
    for (int i = 0; i < thread_count; i++)
    {
        pthread_join(threads[i], NULL);
    }

    // 合并所有已排序的子数组
    long *merge_temp = malloc(count * sizeof(long));
    assert(merge_temp != NULL);
    int current_size = base_step;
    for (int i = 1; i < thread_count; i++)
    {
        int start = 0;
        int mid = current_size;
        int end = mid + base_step;
        if (i == thread_count - 1)
        {
            end += mod;
        }
        merge(result, start, mid, end, merge_temp);
        current_size = end;
    }
    free(merge_temp);

    return result;
}

int main() {
    int count = 10;
    long array[10] = { 4, 8, 3, 10, 6, 7, 5, 1, 9, 2 };
    long *result = merge_sort(array, count);
    print_long_array(result, count);
    free(result);
    return 0;
}

内容的提问来源于stack exchange，提问作者eternal-sphere