How to multithread the merge operation in merge sort?

Question

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?

Answer 1

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

• once both subarrays are sorted,
• assign one thread the task to merge the elements from the beginning of the sorted subarrays to the first half of the target array and
• assign the other thread a different but complementary task: merging from the end of the sorted subarrays to the second half of the target array, starting from the end.
• you must write these merging functions carefully so the sort stays stable and each thread should will only write half of the target array, potentially reading the same elements from the sorted subarrays but selecting different ones.

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