如何修改pthreads并行归并排序函数仅创建一个线程仍获有序结果？

Alright, let's tweak your pthreads-based merge sort to meet your needs. You want the function itself to sort one half of the data, only spawn a single thread for the other half, and keep the original function's parameters/return type untouched. Here's the modified implementation, plus breakdowns of the key changes:

Modified Code #

First, let's assume your original code has a helper thread function and merge logic (I'll include those for completeness, but the only change is to your core merge_sort function):

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

// Thread data structure (unchanged from your original code)
typedef struct {
    int *arr;
    int left;
    int right;
} ThreadData;

// Merge function (unchanged from your original code)
void merge(int *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = malloc(n1 * sizeof(int));
    int *R = malloc(n2 * sizeof(int));
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}

// Thread helper function (unchanged from your original code)
void *merge_sort_thread(void *arg) {
    ThreadData *data = (ThreadData *)arg;
    merge_sort(data->arr, data->left, data->right);
    free(data); // Clean up the thread data
    return NULL;
}

// Your core merge_sort function (MODIFIED - parameters/return type unchanged!)
void merge_sort(int *arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 1. Main thread sorts the left half directly (no thread spawned)
        merge_sort(arr, left, mid);

        // 2. Spawn ONLY ONE thread to sort the right half
        pthread_t right_thread;
        ThreadData *thread_data = malloc(sizeof(ThreadData));
        thread_data->arr = arr;
        thread_data->left = mid + 1;
        thread_data->right = right;
        
        pthread_create(&right_thread, NULL, merge_sort_thread, thread_data);

        // 3. Wait for the right-thread to finish sorting its half
        pthread_join(right_thread, NULL);

        // 4. Merge the two sorted halves
        merge(arr, left, mid, right);
    }
}

Key Changes Explained #

• No parameter/return type changes: The merge_sort function signature stays exactly as you had it—we only modify the internal logic.
• Main thread handles left half: Instead of spawning a thread for both halves, the main thread recursively sorts the left subarray [left, mid] directly. This cuts down on thread creation overhead compared to your original two-thread approach.
• Single thread for right half: We only create one thread to handle the right subarray [mid+1, right]. Using pthread_join ensures we don't start merging until this thread has finished sorting its portion—critical for ensuring the merge step works with two fully sorted halves.
• Reusable helper code: Your existing merge function and merge_sort_thread helper stay completely unchanged, since their roles (merging sorted arrays, wrapping the recursive sort for threads) don't need adjustment.

Quick Notes #

• Make sure you compile with the -pthread flag (e.g., gcc your_file.c -o merge_sort -pthread) to link the pthread library correctly.
• The thread data is freed inside the helper thread, so you don't have to worry about memory leaks from the ThreadData allocations.

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