multithreadingalgorithmsortingmergesort

How to multithread the merge operation in merge sort?


In the multithreaded versions of merge sort that I've seen, the multithreading is typically done during the recursion on the left and right subarray (i.e., each thread is assigned their own subarray to work on) and the merge operation is done by the master thread after each thread completes their individual work.

I am wondering if there's a nice way to multithread the final merge operation where you're merging 2 sorted subarrays? If so, how can this be done?


Solution

  • Actually there is a way to split the merging task among 2 concurrent threads:

    I have not seen this approach mentioned in the literature about multithread merge sort. I wonder if it performs better than classic implementations.