Editing Merge sort (section)

=== Merge sort with parallel recursion ===
The sequential merge sort procedure can be described in two phases, the divide phase and the merge phase. The first consists of many recursive calls that repeatedly perform the same division process until the subsequences are trivially sorted (containing one or no element). An intuitive approach is the parallelization of those recursive calls.<ref name="clrs">{{Harvtxt|Cormen|Leiserson|Rivest|Stein|2009|pp=797–805}}</ref> Following pseudocode describes the merge sort with parallel recursion using the [[Fork–join model|fork and join]] keywords:
 // ''Sort elements lo through hi (exclusive) of array A.''
 '''algorithm''' mergesort(A, lo, hi) '''is'''
     '''if''' lo+1 < hi '''then'''  // ''Two or more elements.''
         mid := ⌊(lo + hi) / 2⌋
         '''fork''' mergesort(A, lo, mid)
         mergesort(A, mid, hi)
         '''join'''
         merge(A, lo, mid, hi)
This algorithm is the trivial modification of the sequential version and does not parallelize well. Therefore, its speedup is not very impressive. It has a [[Analysis of parallel algorithms#Overview|span]] of <math>\Theta(n)</math>, which is only an improvement of <math>\Theta(\log n)</math> compared to the sequential version (see [[Introduction to Algorithms]]). This is mainly due to the sequential merge method, as it is the bottleneck of the parallel executions.