AlgoScope

Sorting

Putting n values in order, and the different prices the algorithms pay to get there.

15 topics9 lessons1 families

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
10514223843576jj+15 > 1

5 is larger than 1, so they swap.

Open in the player →or start at step 2

In this order

  1. Bubble SortSwap neighbours that are out of order until each pass floats one value home.
  2. Selection SortScan for the smallest value left, then swap it home. At most n-1 swaps.
  3. Insertion SortTake the next value and slide it left past larger values into the sorted prefix.
  4. Shell SortInsertion sort with gaps n/2, n/4, ..., 1, so far-apart values move in big strides first.
  5. Merge SortMerge two sorted runs by always taking the smaller front value.
  6. Bottom-Up Merge SortMerge sort with no recursion, doubling the run width on every pass.
  7. Quick SortPick a pivot, push everything smaller left, and the pivot is home for good.
  8. QuickselectPartition like quick sort, but only follow the side that holds the k-th value.
  9. 3-Way Quick SortPartition into smaller, equal and larger zones; the equal zone is final, so duplicates cost O(n).
  10. Heap SortBuild a max-heap in place, then repeatedly swap the root to the end of the shrinking heap and sift the new root down.
  11. Counting SortCount occurrences of each key, prefix-sum the counts, place each element at its final index.
  12. Radix SortCounting-sort by each digit from least significant to most; stability makes it work.
  13. Bucket SortScatter values into equal value ranges, sort each small bucket, gather in order: linear on even data.
  14. TimSortFind natural ascending runs, extend short ones by insertion sort, then merge neighbouring runs.
  15. IntroSortQuick sort that switches to heap sort when recursion gets too deep and to insertion sort on small ranges.

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.

Or a different category

Heap Algorithms

You want the k best, or a stream's current best, rather than the full order.

Searching

You have one question to ask and a single scan costs less than sorting so you can halve it.

Lessons that teach these