Searching and sorting

Finding an item and putting items in order, the two problems that teach most of algorithm analysis: binary search and its traps, the elementary sorts, merge sort and quicksort, the comparison lower bound, sorting in linear time, selection, and how real libraries sort.

This part builds on Linear structures.

2 of 7 topics ready, listed in reading order

SearchingLinear, binary, interpolation and exponential search, with the invariant that keeps binary search correct and the off-by-one traps.Planned

Elementary sortsSelection, bubble and insertion sort, inversions, stability, and best and worst cases traced pass by pass.Planned

Merge sortTop-down and bottom-up merge sort, the merge step, its recurrence, counting inversions and external merging.ReadyQuicksortLomuto and Hoare partitioning, pivot choice, the randomized analysis, three-way partitioning and introsort.Ready

The sorting lower bound and linear-time sortsDecision trees and the comparison lower bound, then counting sort, radix sort and bucket sort.Planned

Selection and order statisticsQuickselect, the median of medians in worst-case linear time, and heaps for the top k items.Planned

Sorting in practiceTimsort and natural runs, key functions and stability, sorting objects, and how to benchmark sorts honestly.Planned