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 потока, пока вы не спуститесь в пустые области.