Sort

1. Uses
   1. Necessary for some algorithms
   2. Speeds processing for others (e.g. sorted index)
   3. Consider other data structures (hash, tree)
2. Radix sort
   1. Sort into bins
   2. O(n), if sort within bin doesn't matter
   3. O(n log n) if you do log n radix sorts
3. Insertion/Bubble sort
   1. Bad to sort from unordered
   2. Not bad for nearly ordered
   3. Good for minor changes
4. O(n log n) sort
   1. quick sort
      • OK, O(n²) if already sorted, O(n log n) average case/randomized
   2. merge sort (heap sort, etc)
5. Parallel sort (bitonic)
   1. Build from max/min steps & swaps
   2. Avoid conditionals
   3. O(log² n) time for n processors
   4. Algorithm
      1. bitonic sequence = /\
      2. cut two bitonic sequences together to build a bigger one (figs from Wikipedia)
      3. 
      4. reorder to unify directions
      5.