Editing Merge sort (section)

==== Multi-sequence selection ====
In its simplest form, given <math>p</math> sorted sequences <math>S_1, ..., S_p</math> distributed evenly on <math>p</math> processors and a rank <math>k</math>, the task is to find an element <math>x</math> with a global rank <math>k</math> in the union of the sequences. Hence, this can be used to divide each <math>S_i</math> in two parts at a splitter index <math>l_i</math>, where the lower part contains only elements which are smaller than <math>x</math>, while the elements bigger than <math>x</math> are located in the upper part.

The presented sequential algorithm returns the indices of the splits in each sequence, e.g. the indices <math>l_i</math> in sequences <math>S_i</math> such that <math>S_i[l_i]</math> has a global rank less than <math>k</math> and <math>\mathrm{rank}\left(S_i[l_i+1]\right) \ge k</math>.<ref>{{cite web |author=Peter Sanders |date=2019 |title=Lecture ''Parallel algorithms'' |url=http://algo2.iti.kit.edu/sanders/courses/paralg19/vorlesung.pdf |access-date=2020-05-02}}</ref>
 '''algorithm'''<nowiki> msSelect(S : Array of sorted Sequences [S_1,..,S_p], k : int) </nowiki>'''is'''
     '''for''' i = 1 '''to''' p '''do''' 
 	(l_i, r_i) = (0, |S_i|-1)
 	
     '''while''' there exists i: l_i < r_i '''do'''
 	// pick Pivot Element in S_j[l_j], .., S_j[r_j], chose random j uniformly
 	v := pickPivot(S, l, r)
 	'''for''' i = 1 '''to''' p '''do''' 
 	    m_i = binarySearch(v, S_i[l_i, r_i]) // sequentially
 	'''if''' m_1 + ... + m_p >= k '''then''' // m_1+ ... + m_p is the global rank of v
 	    r := m  // vector assignment
 	'''else'''
 	    l := m 
 	
     '''return''' l
For the complexity analysis the [[Parallel random-access machine|PRAM]] model is chosen. If the data is evenly distributed over all <math>p</math>, the p-fold execution of the ''binarySearch'' method has a running time of <math>\mathcal{O}\left(p\log\left(n/p\right)\right)</math>. The expected recursion depth is <math>\mathcal{O}\left(\log\left( \textstyle \sum_i |S_i| \right)\right) = \mathcal{O}(\log(n))</math> as in the ordinary [[Quickselect]]. Thus the overall expected running time is <math>\mathcal{O}\left(p\log(n/p)\log(n)\right)</math>.

Applied on the parallel multiway merge sort, this algorithm has to be invoked in parallel such that all splitter elements of rank <math display="inline"> i \frac n p</math> for <math>i = 1,.., p</math> are found simultaneously. These splitter elements can then be used to partition each sequence in <math>p</math> parts, with the same total running time of <math>\mathcal{O}\left(p\, \log(n/p)\log(n)\right)</math>.