Comparison Based Sorting
Required Readings
- Intro to Algorithms
- Pages 773,774,792
- Course Notes
Summary
Sorting Networks
define Sorting Network A fixed circuit that sorts its inputs using a special type of circuit element (or gate) called a comparator. define
An increasing (or plus) comparator puts the maximum number on the bottom
- Decreasing comparator does the opposite
Bitonic Sequences
$define Bitonic Sequence A sequence that starts increasing and changes to decreasing (or vice-versa), as opposed to monotonic.
Or the above can hold for some circular shift. define$
Bitonic sequences are easy to sort
define Bitonic Split When you pair the elements of a bitonic sequence, and apply mins and maxs to the pairs. define
The end result of a bitonic split is two bitonic sequences in the same storage. All of the elements from the ‘max’ pairs are greater than all the elements from the ‘min’.
Bitonic Merge
define Bitonic Merge Split a bitonic sequence until it is sorted. define
bitonicMerge(A[0:n-1])
// Assume A is bitonic
if n >= 2
// assume 2|n
bitonicSplit(A[:])
spawn bitonicMerge(A[0:(n/2)-1])
bitonicMerge(A[n/2:n-1])
sync
You can generate a bitonic sequence from an arbitrary sequence by running multiple bitonic merges
- First of size 2, then 4, then 8, and so on, up to n
Bitonic Sort
Given an arbitrary input, we can generate a bitonic sequence
Given a bitonic sequence, we can sort
genBitonic(a[0:n-1])
if n >= 2
// assume 2|n
spawn genBitonic(A[0:(n/2)-1])
genBitonic(A[n/2:n-1])
sync
spawn bitonicMergePlus(A[0:(n/2)-1])
bitonicMergeMinus(A[n/2:n-1])
sync
bitonicSort(A[0:n-1])
genBitonic(A[:])
bitonicMergePlus(A[:])
Even though this is NOT work optimal, it maps well to things like SIMD and GPU compute.