C ++多线程合并排序不起作用

Question

我是学习 C++ 的新手，我正在尝试实现 MergeSort 的多线程版本。我已经将我的算法与许多在线实现进行了比较，它看起来几乎相同，但是，我没有得到正确的输出。输出甚至包括在原始输入中找不到的数字。

using namespace std;
int a[]  = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};  /* target array */
int arrayLen;

void merge(int low, int mid, int high)
{
    int left = low;
    int right = mid+1;

    int b[high-low+1];
    int i, cur = 0;

    while(left <= mid && right <= high) {
        if (a[left] <= a[right])
            b[cur++] = a[left++];
        else
            b[cur++] = a[right++];
    }

    while(left <= mid) b[cur++] = a[left++];
    while(right <= high) b[cur++] = a[right++];
    cur--;
    while (cur >= 0){
        a[low + cur] = b[cur];
        cur--;
    }
}

void mergeSort(int p, int r){


    std::vector<std::future<void>> thread_poolLocal;
    int q;

    if (p >= r) return;
    q = (p+r)/2;

    thread_poolLocal.push_back( std::async(launch::async, mergeSort, p, q));
    thread_poolLocal.push_back( std::async(launch::async, mergeSort, q+1, r));

    merge(p, q, r);
}

int main()
{
    arrayLen = (sizeof(a)/sizeof(*a));
    cout << "Length of array = " << (sizeof(a)/sizeof(*a)) << endl;

    int i;
    for (i = 0; i < arrayLen; i++) printf ("%d ", a[i]);
    cout << "\n" << endl;
    mergeSort(0, arrayLen);

    for (i = 0; i < arrayLen; i++) printf ("%d ", a[i]);

    return 0;
}

当我用上面显示的简单数组测试它时，输出是：

Length of array = 10
10 9 8 7 6 5 4 3 2 1

0 1 4 2 3 10 5 6 9 7

我正在编译程序：g++ mergeSortThreaded.cpp -o mergeSortThreaded -std=c++0x -pthread

我做错了什么？

Answer 1

您将 2 个线程推入 thread_poolLocal，然后在线程结束前立即调用 merge（需要这些线程的结果）。

此代码可能会导致对较大数组进行排序的线程激增，因为每次调用 mergeSort 都会再创建 2 个线程，直到您到达空白区域。

C ++多线程合并排序不起作用

C++ Multithreaded mergesort not working

c++

multithreading

pthreads

mergesort