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

1. Orders of growth
• "Big-O" notation
• O(n2) (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