Sorting

Insertion sort: most efficient for a small number of elements. take one element in the list at a time, and put it into the correct place in the list (No need to test the first)

Merge-sort: divide-and-conquer recursive algorithm.
1. Divide the list into 1/2.
2. Merge sort each half.
  a. if we have a 1 element list, it is already sorted.
  b. merge lists = take two already sorted lists, and put the lowest of each top element into a new list. (option - add a sentinel item at the end of each input list, with a value of max+1, to save testing for empty. loop will iterate for total number of cards).
The sequential access to already sorted lists makes merge-sort a good choice for linked lists.

Coarsening the leaves: insertion sort is quicker than merge-sort for small n, because of lower constant cost. Therefore it is even more efficient to swap to insertion sort in merge-sort when the divided lists become small enough.

Bubble sort: repeatable swap adjacent elements.

Probabilistic analysis and randomized algorithms (Chapter 5)

The hiring problem

Indicator random variables