Editing Merge sort (section)

==== Basic idea ====
[[File:Parallel_multiway_mergesort_process.svg|alt=|thumb|The parallel multiway mergesort process on four processors <math>t_0</math> to <math>t_3</math>.]]
Given an unsorted sequence of <math>n</math> elements, the goal is to sort the sequence with <math>p</math> available [[Processor (computing)|processors]]. These elements are distributed equally among all processors and sorted locally using a sequential [[Sorting algorithm]]. Hence, the sequence consists of sorted sequences <math>S_1, ..., S_p</math> of length <math display="inline">\lceil \frac{n}{p} \rceil</math>. For simplification let <math>n</math> be a multiple of <math>p</math>, so that <math display="inline">\left\vert S_i \right\vert = \frac{n}{p}</math> for <math>i = 1, ..., p</math>.

These sequences will be used to perform a multisequence selection/splitter selection. For <math>j = 1,..., p</math>, the algorithm determines splitter elements <math>v_j
</math> with global rank <math display="inline">k = j \frac{n}{p}</math>. Then the corresponding positions of <math>v_1, ..., v_p</math> in each sequence <math>S_i</math> are determined with [[Binary search algorithm|binary search]] and thus the <math>S_i</math> are further partitioned into <math>p</math> subsequences <math>S_{i,1}, ..., S_{i,p}</math> with <math display="inline">S_{i,j} := \{x \in S_i | rank(v_{j-1}) < rank(x) \le rank(v_j)\}</math>.

Furthermore, the elements of <math>S_{1,i}, ..., S_{p,i}</math> are assigned to processor <math>i</math>, means all elements between rank <math display="inline">(i-1) \frac{n}{p}</math> and rank <math display="inline">i \frac{n}{p}</math>, which are distributed over all <math>S_i</math>. Thus, each processor receives a sequence of sorted sequences. The fact that the rank <math>k</math> of the splitter elements <math>v_i</math> was chosen globally, provides two important properties: On the one hand, <math>k</math> was chosen so that each processor can still operate on <math display="inline">n/p</math> elements after assignment. The algorithm is perfectly [[Load balancing (computing)|load-balanced]]. On the other hand, all elements on processor <math>i</math> are less than or equal to all elements on processor <math>i+1</math>. Hence, each processor performs the [[K-way merge algorithm|''p''-way merge]] locally and thus obtains a sorted sequence from its sub-sequences. Because of the second property, no further ''p''-way-merge has to be performed, the results only have to be put together in the order of the processor number.