Sorting and searching

How to put things in order, and what order buys you: the ability to find anything in log n steps. Start anywhere. Each one has a live visualizer running the real code.

1. 01Bubble sortSwap neighbours until nothing moves. The one to learn and then never use.O(n²)
2. 02Selection sortFind the smallest, put it first, repeat. Fewest writes of any simple sort.O(n²)
3. 03Insertion sortGrow a sorted prefix one card at a time. Fast on nearly sorted input.O(n²)
4. 04Merge sortSplit in half, sort each half, merge. Always n log n, and stable.O(n log n)
5. 05QuicksortPartition around a pivot, then recurse. Usually the fastest in practice.O(n log n)
6. 06HeapsortBuild a heap, pull the max off n times. n log n with no extra memory.O(n log n)
7. 07Counting sortCount each key instead of comparing. Linear when the keys are small.O(n + k)
8. 08Radix sortSort digit by digit with a stable pass each time.O(d · n)
9. 09Binary searchHalve a sorted range until the target is found or ruled out.O(log n)
10. 10Lower and upper boundBinary search for the first or last position that fits, not just any match.O(log n)