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

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