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

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

$$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.