Editing Merge sort (section)

=== Merge sort with parallel merging ===
{{Main|Merge algorithm#Parallel merge}}
Better parallelism can be achieved by using a parallel [[merge algorithm]]. [[Introduction to Algorithms|Cormen et al.]] present a binary variant that merges two sorted sub-sequences into one sorted output sequence.<ref name="clrs" />

In one of the sequences (the longer one if unequal length), the element of the middle index is selected. Its position in the other sequence is determined in such a way that this sequence would remain sorted if this element were inserted at this position. Thus, one knows how many other elements from both sequences are smaller and the position of the selected element in the output sequence can be calculated. For the partial sequences of the smaller and larger elements created in this way, the merge algorithm is again executed in parallel until the base case of the recursion is reached.

The following pseudocode shows the modified parallel merge sort method using the parallel merge algorithm (adopted from Cormen et al.).
 /**
  * A: Input array
  * B: Output array
  * lo: lower bound
  * hi: upper bound
  * off: offset
  */
 '''algorithm''' parallelMergesort(A, lo, hi, B, off) '''is'''
     len := hi - lo + 1
     '''if''' len == 1 '''then'''
 <nowiki>        B[off] := A[lo]</nowiki>
     '''else''' let T[1..len] be a new array
         mid := ⌊(lo + hi) / 2⌋ 
         mid' := mid - lo + 1
         '''fork''' parallelMergesort(A, lo, mid, T, 1)
         parallelMergesort(A, mid + 1, hi, T, mid' + 1) 
         '''join''' 
         parallelMerge(T, 1, mid', mid' + 1, len, B, off)
In order to analyze a [[recurrence relation]] for the worst case span, the recursive calls of parallelMergesort have to be incorporated only once due to their parallel execution, obtaining

<math display="block"> T_{\infty}^{\text{sort}}(n) = T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + T_{\infty}^{\text{merge}}(n) 
= T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + \Theta \left( \log(n)^2\right).</math>

For detailed information about the complexity of the parallel merge procedure, see [[Merge algorithm#Parallel merge|Merge algorithm]].

The solution of this recurrence is given by

<math display="block"> T_{\infty}^{\text{sort}} = \Theta \left ( \log(n)^3 \right).</math>

This parallel merge algorithm reaches a parallelism of <math display="inline">\Theta \left(\frac{n}{(\log n)^2}\right)</math>, which is much higher than the parallelism of the previous algorithm. Such a sort can perform well in practice when combined with a fast stable sequential sort, such as [[insertion sort]], and a fast sequential merge as a base case for merging small arrays.<ref>Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog [https://duvanenko.tech.blog/2018/01/13/parallel-merge-sort/] and GitHub repo C++ implementation [https://github.com/DragonSpit/ParallelAlgorithms]</ref>