多线程合并排序不能正确排序数组

Question

以下代码应该使用多线程对数组进行归并排序。这个想法是将数组拆分为近似相同大小的子数组，并使用线程对它们进行并发排序。然后，全部排序后（pthread_join的for循环后），再合并到一起。但是，我的代码没有正确排序数组。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <pthread.h>
#include <unistd.h>
#include <assert.h>

typedef struct Arguments
{
    long *nums;
    int start;
    int end;
    long *result;
} SortThreadArgs;

/** The number of threads to be used for sorting. Default: 1 */
int thread_count = 2;
pthread_mutex_t merge_lock;

/**
 * Print the given array of longs, an element per line.
 */
void print_long_array(const long *array, int count)
{
    for (int i = 0; i < count; ++i)
    {
        printf("%ld\n", array[i]);
    }
}

/**
 * Merge two slices of nums into the corresponding portion of target.
 */
void merge(long nums[], int from, int mid, int to, long target[])
{
    int left = from;
    int right = mid;

    // acquire lock before accessing shared data
    pthread_mutex_lock(&merge_lock);

    int i = from;
    for (; i < to && left < mid && right < to; i++)
    {
        if (nums[left] <= nums[right])
        {
            target[i] = nums[left];
            left++;
        }
        else
        {
            target[i] = nums[right];
            right++;
        }
    }
    if (left < mid)
    {
        memmove(&target[i], &nums[left], (mid - left) * sizeof(long));
    }
    else if (right < to)
    {
        memmove(&target[i], &nums[right], (to - right) * sizeof(long));
    }

    // release lock after modifying shared data
    pthread_mutex_unlock(&merge_lock);
}

/**
 * Sort the given slice of nums into target.
 *
 * Warning: nums gets overwritten.
 */
void merge_sort_aux(long nums[], int from, int to, long target[])
{
    if (to - from <= 1)
    {
        return;
    }

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

void *sort_thread(void *arg)
{
    SortThreadArgs *args = (SortThreadArgs *)arg;
    long *nums = args->nums;
    int start = args->start;
    int end = args->end;
    long *result = args->result;

    merge_sort_aux(nums, start, end, result);

    pthread_exit(NULL);
}

/**
 * Sort the given array and return the sorted version.
 *
 * The result is malloc'd so it is the caller's responsibility to free it.
 *
 * Warning: The source array gets overwritten.
 */
long *merge_sort(long nums[], int count)
{
    // Check if thread_count is divisible by count
    int mod = count % thread_count;

    // Create a temp array that has the same elements as the given array
    long *result = calloc(count, sizeof(long));
    assert(result != NULL);
    memmove(result, nums, count * sizeof(long));

    pthread_mutex_init(&merge_lock, NULL);

    pthread_t threads[thread_count];
    for (int i = 0; i < thread_count; i++)
    {
        // Calculate the start and end index based on the thread_num
        // i.e. Splitting the array into approximately same-size sub arrays
        int start = i * (count / thread_count);
        int end;
        if (i == thread_count - 1 && mod != 0) {
            end = count;
        } else {
            end = (i + 1) * (count / thread_count);
        }
        SortThreadArgs args = {nums, start, end, result};
        pthread_create(&threads[i], NULL, sort_thread, &args);
    }

    for (int i = 0; i < thread_count; i++)
    {
        pthread_join(threads[i], NULL);
    }

    // perform final merge operation on all subarrays
    for (int i = 0; i < thread_count; i++)
    {
        int start = i * (count / thread_count);
        int mid = start;
        int end;
        if (i == thread_count - 1 && mod != 0) {
            end = count;
        } else {
            end = (i + 1) * (count / thread_count);
        }
        merge(nums, 0, mid, end, result);
    }

    pthread_mutex_destroy(&merge_lock);

    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);
}

我将数组拆分为子数组的方式是在 merge_sort 函数的第一个循环中。根据计数器 i，我计算开始和结束索引。例如，如果 thread_count = 2 且 count = 10，则对于 i = 0，start = 0，end = 5；对于 i = 1，开始 = 5，结束 = 10.

数组

{4, 8, 3, 10, 6, 7, 5, 1, 9, 2}

中，打印输出为：

1 2 2 4 5 8 3 9 10 6

这真的很奇怪，因为有一个重复的 2。假设我的想法应该正确工作，但我真的不知道导致这个的潜在错误是什么。任何帮助表示赞赏！

当我尝试在

pthread_join

之后的for循环中打印每个子数组时，它显示子数组甚至没有排序。

---

编辑：

我稍微清理了我的代码并按照建议将 memmove 更改为 memcpy。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <pthread.h>
#include <unistd.h>

#include <assert.h>

/** The number of threads to be used for sorting. Default: 1 */
int thread_count = 1;

typedef struct Arguments
{
    long *nums;
    int from;
    int to;
    long *target;
} merge_sort_args;

/**
 * Print the given array of longs, an element per line.
 */
void print_long_array(const long *array, int count)
{
    for (int i = 0; i < count; ++i)
    {
        printf("%ld\n", array[i]);
    }
}

/**
 * Merge two slices of nums into the corresponding portion of target.
 */
void merge(long nums[], int from, int mid, int to, long target[])
{
    printf("here\n");
    int left = from;
    int right = mid;

    int i = from;
    for (; i < to && left < mid && right < to; i++)
    {
        if (nums[left] <= nums[right])
        {
            target[i] = nums[left];
            left++;
        }
        else
        {
            target[i] = nums[right];
            right++;
        }
    }
    if (left < mid)
    {
        memcpy(&target[i], &nums[left], (mid - left) * sizeof(long));
    }
    else if (right < to)
    {
        memcpy(&target[i], &nums[right], (to - right) * sizeof(long));
    }
}

/**
 * Sort the given slice of nums into target.
 *
 * Warning: nums gets overwritten.
 */
void *merge_sort_aux(void *arg)
{
    merge_sort_args *msa = (merge_sort_args *)arg;
    long *nums = msa->nums;
    int from = msa->from;
    int to = msa->to;
    long *target = msa->target;
    if (to - from <= 1)
    {
        pthread_exit(NULL);
    }

    int mid = (from + to) / 2;
    merge_sort_args left_args = {target, from, mid, nums};
    merge_sort_aux(&left_args);
    merge_sort_args right_args = {target, mid, to, nums};
    merge_sort_aux(&right_args);
    merge(nums, from, mid, to, target);

    pthread_exit(NULL);
}

/**
 * Sort the given array and return the sorted version.
 *
 * The result is malloc'd so it is the caller's responsibility to free it.
 *
 * Warning: The source array gets overwritten.
 */
long *merge_sort(long nums[], int count)
{
    long *result = calloc(count, sizeof(long));
    assert(result != NULL);

    memcpy(result, nums, count * sizeof(long));

    pthread_t threads[thread_count];
    // Split the array into sub arrays here
    for (int i = 0; i < thread_count; i++)
    {
        int start = i * (count / thread_count);
        int end = (i + 1) * (count / thread_count);
        merge_sort_args args = {nums, start, end, result};
        pthread_create(&threads[i], NULL, merge_sort_aux, &args);
    }

    for (int i = 0; i < thread_count; i++)
    {
        pthread_join(threads[i], NULL);
    }

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

    return result;
}

int main()
{
    long array[2] = {2, 1};
    int count = 2;
    long *result = merge_sort(array, count);
    print_long_array(result, count);
}

这次我在一个非常小的数组上尝试

2 1

，但我发现它甚至没有进入

merge

函数，因为它没有打印出标志。可能是什么原因？