Chapter 7 of 10All chapters
Chapter 7 of 10
Sorting and searching
The classics, and when to write one.
The algorithms
Merge sort splits and merges in guaranteed O(n log n). Quicksort partitions around a pivot, faster in practice but O(n squared) in the worst case. Insertion sort wins on tiny or nearly sorted input.
- Your language's built-in sort is a tuned hybrid. Use it.
- Sorting first is often what makes the next step cheap.
Binary search
On sorted data, halving the range each step finds an item in logarithmic time. It also finds insertion points and boundaries, which is where it earns its keep beyond the textbook.