Comparison Based Sorting

Required Readings

• Intro to Algorithms
  • Pages 773,774,792
• Course Notes

Summary

• Sorting Networks
• Bitonic Sequences
  • Bitonic Merge
  • Bitonic Sort

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[:])

$$W_{bs}(n) = \Theta(nlog^2n)$$

$$D_{bs}(n) = \Theta(log^2n)$$

Even though this is NOT work optimal, it maps well to things like SIMD and GPU compute.