Editing Merge sort (section)

====Analysis====
Firstly, each processor sorts the assigned <math>n/p</math> elements locally using a sorting algorithm with complexity <math>\mathcal{O}\left( n/p \; \log ( n/p) \right)</math>. After that, the splitter elements have to be calculated in time <math>\mathcal{O}\left(p \,\log(n/p) \log (n) \right)</math>. Finally, each group of <math>p</math> splits have to be merged in parallel by each processor with a running time of <math>\mathcal{O}(\log(p)\; n/p  )</math> using a sequential [[Merge algorithm|p-way merge algorithm]]. Thus, the overall running time is given by

<math>\mathcal{O}\left( \frac n p \log\left(\frac n p\right) + p \log \left( \frac n p\right) \log (n) + \frac n p \log (p) \right)</math>.