Sorting
Putting n values in order, and the different prices the algorithms pay to get there.
Bubble Sort: Seven values
Every comparison sort answers the same question and differs only in which comparisons it decides to make. Bubble, selection and insertion sort each make about n squared over 2 of them and move values one slot at a time. Merge sort, quick sort and heap sort reach n log n by splitting the work roughly in half at every level, so there are log n levels and each costs O(n).
n log n is the floor for comparison sorting: there are n factorial possible orders, a comparison yields one bit, and no sequence of fewer than about n log n bits can distinguish them. The linear sorts get underneath it by not comparing at all. Counting sort tallies how many of each key there are and works out every element's final index from the running totals. Radix sort applies that once per digit and depends on each pass being stable. Both cost O(n + k) for a key range of size k, which is why they suit small integers rather than arbitrary values.
Past the big-O the differences are memory, stability and the worst case. Merge sort needs a second array. Quick sort sorts in place but degrades to n squared on an unlucky pivot. Heap sort is in place with no bad case but a larger constant per element. Library sorts mix them: TimSort finds runs that are already in order and merges them, IntroSort starts as quick sort and switches to heap sort when the recursion gets too deep.
After this you can
- Trace each sort on a small array and count the comparisons and swaps it made
- Say which sorts are stable, which are in place, and where each one's worst case comes from
- Explain why comparison sorting cannot beat n log n, and how counting and radix sort avoid the bound
- Partition once to find the k-th smallest value without sorting the rest
- Say why a library sort changes algorithm partway through a single call
In this order
Where people go wrong
A fixed pivot on sorted input
Taking the first or last element as the pivot splits an already sorted array into nothing and everything, so quick sort does n levels of n work. Sorted input is exactly what you are likely to be handed. Pick a random element or the median of three.
Stability is not a detail
Sorting by city and then by name only produces the grouping you wanted if the second sort leaves equal names in their existing order. Merge, insertion and counting sort do. Selection, quick and heap sort do not.
Reading the asymptotics at n = 20
Insertion sort beats merge sort on short arrays because its per-element work is a comparison and a shift, and it does almost nothing when the data is already ordered. That is why TimSort and IntroSort hand small ranges to it.