c++ - 线程合并排序给出无效结果

Question

我创建了一个合并排序，它适用于非重复整数数组。我正在尝试制作相同的多线程版本。

我得到无效的结果。

void mergesort(int data[ ], size_t n)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray

    if (n > 1)
    {
        // Compute sizes of the subarrays.
        n1 = n / 2;
        n2 = n - n1;

        mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        mergesort((data + n1), n2);  // Sort from data[n1] to the end

        // Merge the two sorted halves.
        merge(data, n1, n2);
    }
}

DWORD WINAPI threadedmergesort(LPVOID params)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray
    Params* parameters = (Params*) params;
    if (parameters->size > 1)
    {
        // Compute sizes of the subarrays.
        n1 = parameters->size / 2;
        n2 = parameters->size - n1;

        Params* p1 = new Params(parameters->dataArray, n1);
        //mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        Params* p2 = new Params(parameters->dataArray, n2);
        //mergesort((data + n1), n2);  // Sort from data[n1] to the end
        HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        WaitForSingleObject(h1, INFINITE);
        WaitForSingleObject(h2, INFINITE);

        // Merge the two sorted halves.
        merge(parameters->dataArray, n1, n2);
    }
    return (DWORD)0x0; //null
}

struct Params
{
    int* dataArray;
    int size;
    Params(int _dataArray[], int _size);
};
Params::Params(int _dataArray[], int _size)
{
    dataArray = _dataArray;
    size = _size;
}

有人可以评论一下为什么我使用合并排序的线程版本会得到无效结果，以及我可以做些什么来纠正这个问题吗？

Answer 1

Params* p1 = new Params(parameters->dataArray, n1);
//mergesort(data, n1);         // Sort from data[0] through data[n1-1]
HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
Params* p2 = new Params(parameters->dataArray, n2);
//mergesort((data + n1), n2);  // Sort from data[n1] to the end
HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);

看起来您向合并排序器发送了两次 p1。所以你只是对列表的前半部分进行排序。更改你的第二个参数，一切都应该是正确的。

我的合并排序看起来像这样:

DWORD WINAPI Mergesorter::mergesort_MT(LPVOID param)
{
    Mergesort_Params* i_mergesortParams = (Mergesort_Params*)param;
    unsigned int half = i_mergesortParams->numberOfValues / 2;
    DWORD threadId[2] = {0,0};
    HANDLE h[2];
    Mergesort_Params* mergesortParams;

    if(i_mergesortParams->numberOfValues > 1)
    {
        mergesortParams = new Mergesort_Params[2];
        mergesortParams[0].l_list = i_mergesortParams->l_list;
        mergesortParams[1].l_list = i_mergesortParams->l_list + half;
        mergesortParams[0].numberOfValues = half;
        mergesortParams[1].numberOfValues = i_mergesortParams->numberOfValues - half;

        h[0] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[0],0,&threadId[0]);
        //WaitForSingleObject(h[0],INFINITE);
        h[1] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[1],0,&threadId[1]);        
        //WaitForSingleObject(h[1],INFINITE);
        WaitForMultipleObjects(2,h,TRUE,INFINITE);
        merge_ST(i_mergesortParams->l_list,half,i_mergesortParams->numberOfValues - half);


    }

//delete threadId;
//delete h;
//delete mergesortParams;

return 0;
}

你的问题解决了吗？现在我的问题是，我无法对足够的值进行排序，100000 太多了(单线程没问题)并且我的 CPU 没有完全使用(我的 A8-3500M 上有 25%，所以只有一个核心)