Content deleted Content added
No edit summary |
No edit summary |
||
Line 51:
=== Distribution sort ===
[[Distribution sort]] partitions an input list <math>A</math>of size <math>N</math>into <math>d</math>disjoint buckets of similar size. Every bucket is then sorted recursively and the results are combined into a fully sorted list.
If <math>P = 1</math>the task is delegated to a cache-optimal single-processor sorting algorithm.
== Other algorithms ==▼
Otherwise the following algorithm is used:
// Sample <math>\tfrac{4N}{\sqrt{d}}</math>elements from <math>A</math>
'''for''' '''each''' processor <math>i</math>'''in parallel do'''
'''if''' <math>M < |S_i|</math>'''then'''
<math>d = M/B</math>
Load <math>S_i</math>in <math>M</math>-sized pages and sort pages individually
'''else'''
<math>d = |S_i|</math>
Load and sort <math>S_i</math>as single page
'''end if'''
Pick every <math>\sqrt{d}/4</math>'th element from each sorted memory page into contiguous vector <math>R^i</math>of samples
'''end for'''
'''in parallel do'''
Combine vectors <math>R^1 \dots R^P</math>into a single contiguous vector <math>\mathcal{R}</math>
Make <math>\sqrt{d}</math>copies of <math>\mathcal{R}</math>: <math>\mathcal{R}_1 \dots \mathcal{R}_{\sqrt{d}}</math>
'''end do'''
// Find <math>\sqrt{d}</math>pivots <math>\mathcal{M}[j]</math>
'''for''' <math>j = 1</math>to <math>\sqrt{d}</math>'''in parallel do'''
<math>\mathcal{M}[j] = \texttt{PEMSELECT}(\mathcal{R}_i, \tfrac{P}{\sqrt{d}}, \tfrac{j \cdot 4N}{d})</math>
'''end for'''
Pack pivots in contiguous array <math>\mathcal{M}</math>
// Partition <math>A</math>around pivots into buckets <math>\mathcal{B}</math>
<math>\mathcal{B} = \texttt{PEMMULTIPARTITION}(A[1:N],\mathcal{M},\sqrt{d},P)</math>
// Recursively sort buckets
'''for''' <math>j = 1</math>to <math>\sqrt{d} + 1</math>'''in parallel do'''
recursively call <math>\texttt{PEMDISTSORT}</math>on bucket <math>j</math>of size <math>\mathcal{B}[j]</math>
using <math>O \left( \left \lceil \tfrac{\mathcal{B}[j]}{N / P} \right \rceil \right)</math>processors responsible for elements in bucket <math>j</math>
'''end for'''
<br />{{Collapse|Lorem Ipsum|<code>PEMDISTSORT</code> pseudocode}}<br />
▲=== Other algorithms ===
{| class="wikitable"
|+
Line 61 ⟶ 97:
!Space complexity
|-
!PEM [[Merge sort|Mergesort]]<ref name=":0" />
|Sorts a list of items
|<math>O\left(\frac{N}{PB} \log_{\frac{M}{B}} \frac{N}{B}\right) \textrm{ if } \; P \leq \frac{N}{B^2}, M = B^{O(1)}</math>
| |||