Comparison Based Sorting
Required Readings
- Intro to Algorithms
- Pages 773,774,792
- Course Notes
Summary
Sorting Networks
Sorting Network
A fixed circuit that sorts its inputs using a special type of circuit element (or gate) called a comparator.
An increasing (or plus) comparator puts the maximum number on the bottom
- Decreasing comparator does the opposite
Bitonic Sequences
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.
Bitonic sequences are easy to sort
Bitonic Split
When you pair the elements of a bitonic sequence, and apply mins and maxs to the pairs.
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
Bitonic Merge
Split a bitonic sequence until it is sorted.
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.