Stuff I would study if I were preparing for the sorting test

1. Orders of growth
• "Big-O" notation
  • O(n²) (quadratic growth): Bubble, Insertion, and Selection sorts and degenerate Quick sort
  • O(nlogn) (linearithmic growth): Quick, Heap, and Merge sorts
  • O(n) (linear growth): Time it takes to search a linear data structure such as an array or list
  • O(logn) (logarithmic growth): Time it takes to search a balanced binary search tree (chopping data size in half at each step)
  • O(1) (constant growth): Time it takes to access an element in an array or ArrayList or HashMap (not dependent on n)
2. Mechanics of how the different sorting routines work
   • Bubble: Side-by-side comparisons, typically moving bigger values to the right
   • Insertion: Data in front is already sorted; grab next datum and insert it into the sorted data
   • Selection: Find the next smallest datum and swap it into place
   • Quick: Use a pivot and put smaller stuff to left, larger to right, then recursively call on left and right
   • Heap: Build a max-heap (or min-heap) and then sort it by swapping data at top of heap into last unsorted position in data structure
   • Merge: Chop data in half, until down to groups of 1 and 0; then merge together into one data structure