Merge sort
Basic Idea

Furthermore, the elements of S 1, i,..., S p, i {\displaystyle S_{1,i},...,S_{p,i}} are assigned to processor i {\displaystyle i}, means all elements between rank (i − 1) n p {\textstyle (i-1){\frac {n}{p}}} and rank i n p {\textstyle i{\frac {n}{p}}}, which are distributed over all S i {\displaystyle S_{i}}. Thus, each processor receives a sequence of sorted sequences. The fact that the rank k {\displaystyle k} of the splitter elements v i {\displaystyle v_{i}} was chosen globally, provides two important properties: On the one hand, k {\displaystyle k} was chosen so that each processor can still operate on n / p {\textstyle n/p} elements after assignment. The algorithm is perfectly load-balanced. On the other hand, all elements on processor i {\displaystyle i} are less than or equal to all elements on processor i + 1 {\displaystyle i+1}. Hence, each processor performs the 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.
change_case:english_capital