Algorithm Design Manual - Booknotes
Factors:
Increasing or decreasing order?
Sorting the key or entire record?
Equal keys. Now what?
Non-numerical data. Now what?
Heapsort
A heap-labeled tree = a binary tree such that the key of each node "dominates" the keys of its children. You can store a binary tree in an array w/o pointers - space efficient, but missing nodes take up unused space.
Mergesort
Partition elements into two groups, sort each smaller problem recursively, then interleave two sorted lists to order the merged elements.
Quicksort
Distribution Sort
Ex: sorting phone book by 1st letter of last name ==> 26 buckets. Repeat with 2nd letter of last name (smaller piles), etc. Done when each bucket contains a single name.
Effective when distribution is roughly uniform, terrible when not.
Binary Search & Related algos
Fast algorithm for searching a sorted array of keys.