Analyzing Algorithms: Searching and Sorting

Analyzing an algorithm simply means counting how many basic steps (here, comparisons) it takes, as a function of how much data it gets. It's good for picking the right tool before you write a line of code. All we're really saying in this lesson is that cutting a problem in half, over and over, gets you to the bottom shockingly fast. The formula $T(n) = 2T(n/2) + n$ looks intimidating, but read it piece by piece: $T(n)$ (the work to sort $n$ items) equals $2T(n/2)$ (sorting two half-size lists) plus $n$ (the work to merge them back together). And $n\log_2 n$ just means "$n$ work, done $\log_2 n$ times," once for each time you can halve the list. Now that we can compare growth rates, let's use big-O on the two jobs computers do constantly: finding things and putting things in order.

Searching. Linear search checks items one by one, so it can take up to $n$ comparisons. But if the list is sorted, you can do much better, the same way you'd look up a word in a dictionary. Binary search compares with the middle item. If the target is smaller, the whole right half can't contain it, so you throw that half away (and the left half if it's bigger). After $k$ steps at most $n/2^k$ items remain, and that hits 1 once $2^k \ge n$, so about $\log_2 n$ steps are enough. That's 20 comparisons for a million items.

Simple sorting. Selection sort finds the smallest item, then the next smallest, and so on, which ends up comparing every pair once: $\binom{n}{2} = \frac{n(n-1)}{2}$ comparisons, so $O(n^2)$.

Merge sort. Here's where halving helps with sorting too. Split the list in half, sort each half recursively, then merge the two sorted halves. Merging is cheap: the smallest remaining item is always at the front of one of the two halves, so each comparison places one item, and it takes at most $n$ comparisons. That gives $T(n) = 2T(n/2) + n$. To see what this solves to, picture the recursion tree. The list can be halved $\log_2 n$ times, so there are $\log_2 n$ levels, and on every level the pieces add up to $n$ items, so each level does $n$ work in total. That makes $T(n) = n\log_2 n$, which induction confirms.

No comparison sort can do better. Think about what a sort has to figure out: which of the $n!$ possible orderings it was handed. Each comparison has two outcomes, so $k$ comparisons can tell apart at most $2^k$ cases. To cover all $n!$, some input needs at least $\log_2(n!) \approx n\log_2 n$ comparisons. So merge sort is optimal up to a constant factor.

Every database index, search engine and spreadsheet sort relies on O(log n) searching and O(n log n) sorting.