Searching & Sorting
The problem
Finding an item and putting items in order are two of the most common operations in computing, and the difference between a naive and a clever approach is the difference between a program that scales and one that doesn't — this topic is where complexity analysis first pays off concretely.
Why now
Complexity analysis gives the vocabulary to compare approaches; recursion gives the technique (divide and conquer) the fastest sorting algorithms rely on. This topic is the first place both get applied together to derive genuinely different-shaped algorithms for the same problem, with measurably different costs.
Mental model
Searching an unordered list means checking everything — O(n) — but searching a sorted one lets you throw away half the remaining space each step, the same halving idea from logarithms. Sorting algorithms split into two families: comparison-based (merge sort, quicksort — divide, solve, combine) bounded at O(n log n), and non-comparison approaches that exploit structure in the data to go faster.
Requires
- Complexity Analysis in PracticeComputer Science Fundamentals
Comparing search and sort algorithms is the direct payoff of complexity analysis — without it there's no principled way to say merge sort 'beats' bubble sort beyond a vague sense of speed.
- RecursionProgramming Fundamentals
Binary search and the fastest sorting algorithms (merge sort, quicksort) are divide-and-conquer, which is recursion applied to shrink a problem by discarding or splitting it each call.
Used in
- Array.prototype.sort and every language's built-in sort function
- Database ORDER BY and index-based lookups
- Binary search across sorted datasets and version-control bisection (git bisect)
- Search engines ranking and retrieving results
Projects
- Implement binary search, merge sort, and quicksort from scratch, then benchmark all three against the built-in sort on increasingly large inputs
- Deliberately construct a worst-case input for quicksort (already-sorted data with a naive pivot) and observe the O(n²) degradation
Examples
- Binary search on a sorted 1,000,000-item array takes ~20 comparisons; linear search takes up to 1,000,000
- Merge sort's guaranteed O(n log n) versus quicksort's average O(n log n) but worst-case O(n²) is a real engineering tradeoff, not just trivia
Resources
Mastery checklist
- I can implement binary search correctly, including off-by-one edge cases
- I can implement merge sort and explain why it's always O(n log n)
- I can explain why quicksort's worst case is O(n²) and how pivot choice affects it
- I can choose an appropriate search or sort strategy given data size and ordering constraints