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

- Orders of growth
- "Big-O" notation
- O(n
^{2}) (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)

- 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