使用两个线程实现递归归并排序的索引异常问题求助

从你的输出和代码来看，核心问题出在区间划分逻辑错误、线程参数管理不当以及局部变量生命周期这几个方面，我们一步步来解决：

问题1：区间划分错误（low > high的直接原因） #

你在触发线程排序的分支里，计算左半区的high时用了h/2，这是完全错误的！比如当当前处理的区间是[4,7]时，h/2等于3，左半区的low是4，high是3，自然就出现了low > high的异常。

正确的区间划分应该基于当前的l和h计算中间位置，而不是直接用h/2。对于区间[l, h]，中间位置应该是：

int mid = l + (h - l) / 2; // 避免溢出的安全写法，等价于 (l + h) / 2

问题2：线程参数的生命周期与覆盖问题 #

1. 你定义的thread_data_array是函数局部变量，当Recursive_Divition函数返回后，这块内存会被回收，但线程可能还在读取这些参数，导致未定义行为。
2. count是按值传递的，每个递归调用的count都是独立副本，会导致不同递归层次的线程重复使用thread_data_array的同一个索引，参数被覆盖。

解决办法是为每个线程动态分配独立的参数结构体，在线程函数中使用完成后释放它。

问题3：停止条件过于严格 #

当前你只在len == 2*Degree_of_parallelism时才创建线程，这会导致大部分情况下无法触发并行逻辑。合理的逻辑应该是：当数组长度大于某个阈值（比如并行度）时，要么继续递归划分，要么创建线程处理子区间；当长度较小时，直接用串行排序（比如插入排序），避免线程创建的开销。

修复后的代码示例 #

修改后的Recursive_Divition函数 #

void Recursive_Divition(int a[], int l, int h, int Degree_of_parallelism) {
    int len = h - l + 1;

    // 小尺寸数组用串行插入排序，避免线程开销
    if (len <= Degree_of_parallelism) {
        insertionSort(a, l, h); // 假设你有实现insertionSort
        return;
    }

    // 当数组足够大时，判断是否创建线程处理子区间
    if (len <= 2 * Degree_of_parallelism) {
        pthread_t thread1, thread2;
        // 为每个线程分配独立的参数
        struct thread_data *data1 = malloc(sizeof(struct thread_data));
        struct thread_data *data2 = malloc(sizeof(struct thread_data));

        int mid = l + (h - l) / 2;
        data1->low = l;
        data1->high = mid;
        data2->low = mid + 1;
        data2->high = h;

        // 创建线程
        pthread_create(&thread1, NULL, threaded_merge_sort, (void *)data1);
        pthread_create(&thread2, NULL, threaded_merge_sort, (void *)data2);

        // 等待线程完成
        pthread_join(thread1, NULL);
        pthread_join(thread2, NULL);

        // 合并两个有序子区间
        merge(a, l, mid, h);
        return;
    }

    // 数组更大时，继续递归划分
    int mid = l + (h - l) / 2;
    Recursive_Divition(a, l, mid, Degree_of_parallelism);
    Recursive_Divition(a, mid + 1, h, Degree_of_parallelism);
    merge(a, l, mid, h);
}

修改后的threaded_merge_sort函数 #

void *threaded_merge_sort(void *param) {
    printf("Create a thread %u\n", (unsigned int)pthread_self());
    struct thread_data *my_data = (struct thread_data *)param;
    int l = my_data->low;
    int h = my_data->high;
    printf("low is : %d high is : %d\n", l, h);

    // 串行排序子区间
    mergeSort(array, l, h);

    // 释放动态分配的参数
    free(my_data);
    pthread_exit(NULL);
}

额外注意事项 #

• 确保array是全局变量或者通过参数传递给threaded_merge_sort（当前你的代码里用了全局array，如果是局部变量需要调整参数传递）。
• 插入排序insertionSort需要你自己实现，用于小尺寸数组的串行排序，比创建线程更高效。
• 合并函数merge要确保逻辑正确，这是归并排序的核心，若合并出错也会导致排序结果异常。

这样修改后，你就不会再出现low > high的索引异常，线程参数也不会被覆盖或访问无效内存，排序结果应该能符合预期了。

内容的提问来源于stack exchange，提问作者诇讜讗讬 讙讘专