You have 9 unsorted numbers and a simple question: what's the 3rd smallest?

The most obvious approach is to sort the entire array and read off position 2 (zero-indexed). Sorting puts every element in its correct position. You'd know the 1st smallest, the 2nd smallest, the 3rd, the 4th — all of them.

But you only asked about one of them. Sorting answers 9 questions when you only asked 1. That feels like a lot of wasted work.

How much waste, exactly? Drag the slider — watch the gap between “sorted” and “needed” grow as the array gets larger.

At small sizes the waste barely registers. At n = 1,000 you're sorting 999 elements you never asked about. That ratio only gets worse.

Let's make the waste concrete. You're going to sort an array to find a single element — watch how many comparisons the sort algorithm performs, and how many of those comparisons actually help locate the element you care about. The gap between “total work done” and “useful work done” is the cost of answering questions nobody asked.

Sorting did O(n log n) comparisons to answer a question about a single element. Most of those comparisons were spent putting elements into positions you never cared about.

What if there were a way to find just the element you want, without fully sorting everything else? You'd need some way to narrow down the candidates — to eliminate elements that definitely aren't the answer — without doing the full work of putting every element in order.

Here's the core idea: pick one element as a pivot and split the array into two groups — everything less than the pivot, and everything greater. Then count which group your target falls into. The other group? Throw it away entirely.

Tap different elements to try them as pivot — watch how the split changes and which side gets discarded.

Notice how the pivot choice determines how much you eliminate. A pivot near the middle discards half the array. A pivot at an extreme discards almost nothing. That asymmetry will matter later.

Let's try this elimination strategy and see how many elements you can discard at each step.

Time to try the partition-and-discard strategy yourself. You'll pick a pivot, split the array, and then decide which side to keep. At each step, count how many elements you're throwing away — that's the whole point. You're not ordering anything. You're just narrowing down the search space, one partition at a time.

Notice the pattern: at each step, you partition the array around a pivot, figure out which side contains your target, and throw away the other side entirely. The problem gets smaller every time.

In merge sort, you recurse into both halves. Here, you only recurse into one. That's a fundamentally different shape of recursion — and it leads to a fundamentally different amount of work.

If each partition cuts the problem roughly in half, the work at each level is: n, then n/2, then n/4, then n/8... That's a geometric series. But does it converge to something meaningful, or does it blow up?

Keep adding levels and watch the running total. No matter how many you add, it never reaches 2n.

Each bar gets smaller. The total creeps toward 2n but never arrives. That's not obvious — the harmonic series (1 + 1/2 + 1/3 + ...) also has shrinking terms but diverges to infinity. Let's prove why this one converges.

You saw the bars shrinking — each recursive level does roughly half the work of the one before it. That sure looks like it converges, but “looks convergent” isn't a proof. Plenty of sequences look like they're shrinking and still blow up (the harmonic series 1 + 1/2 + 1/3 + ... never stops growing, even though each term gets smaller).

So let's nail this down. The total work across all levels is n + n/2 + n/4 + n/8 + ... — can you figure out what that actually sums to? Build the sum step by step and watch the running total.

The sum n + n/2 + n/4 + n/8 + ... converges to 2n. Not n log n. Not n^2. Just 2n — which is O(n).

This is one of the most surprising results in algorithm design. By doing less at each recursive level (only recursing into one half instead of both), you don't just save a constant factor — you drop an entire logarithmic term from the complexity.

Drag the slider to watch the gap between sort and quickselect widen. At small sizes, the difference is modest. At n = 10,000, quickselect does a fraction of the work.

Merge sort is O(n log n) because it recurses into both halves: n work at each of log n levels. This single-branch approach is O(n) because the total work across all levels forms a convergent series.

We've been assuming the pivot splits the array roughly in half. That's the happy path — and the analysis above depends on it. But what happens if you're unlucky?

Imagine you're looking for the 3rd smallest element in an array of 100 items. You pick a pivot, partition, and... the pivot turns out to be the smallest element in the array. Everything lands in the “greater than” group. You eliminated exactly 1 element and still have 99 left. Next round, you pick another bad pivot — the smallest of the remaining 99. You eliminate 1 more. Still 98 to go.

See the pattern? Each round does O(n) work to partition, but only eliminates a single element. The total work becomes: n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n^2).

That's the same complexity as brute force. The whole divide-and-conquer strategy collapsed because the “divide” step barely divided anything.

This isn't hypothetical. If the array is already sorted and you always pick the first element as the pivot, every partition is maximally lopsided. The recursion tree degenerates from a balanced binary structure into a linked list — the same pathology that turns quicksort from O(n log n) into O(n^2).

Drag the slider to feel how pivot quality controls everything. At 50% (median), depth is logarithmic and total work is about 2n. Slide toward 0% and watch both numbers explode.

So quickselect has O(n) expected time (when pivots land near the median on average) but O(n^2) worst case (when pivots consistently land at the extremes). The “expected” qualifier is doing a lot of heavy lifting there. In practice, randomizing the pivot choice makes the worst case astronomically unlikely — but it doesn't eliminate it entirely.

This is exactly the kind of gap that shows up in interviews. LC 215 (Kth Largest Element in an Array) is the classic quickselect problem. A randomized pivot gets you past the time limit in practice, but an interviewer might ask: "Can you guarantee O(n)?"

Now let's see how this single-branch recursion translates into actual code. The algorithm is called quickselect (sometimes called Hoare's selection algorithm), and it's closely related to quicksort — same partition step, different recursive structure. The key difference: after partitioning, quicksort recurses into both sides. Quickselect checks which side contains the target index and recurses into only that one.

Pay attention to the moment the recursion branches. In quicksort you'd see two recursive calls. Here you'll see an if/else — one path discarded entirely.

function quickselect(arr: number[], k: number): number {

  if (arr.length === 1) return arr[0];

  const pivot = arr[Math.floor(Math.random() * arr.length)];

  const left  = arr.filter(x => x < pivot);

  const equal = arr.filter(x => x === pivot);

  const right = arr.filter(x => x > pivot);

  if (k <= left.length) {

    return quickselect(left, k);

  } else if (k <= left.length + equal.length) {

    return pivot;  // Found it!

  } else {

    return quickselect(right, k - left.length - equal.length);

  }

}

You've just built an O(n) algorithm for a problem that “obviously” requires sorting. The strategy was simple: partition once to place a pivot in its correct position, check whether your target is to the left or right of that pivot, and recurse into only the relevant side.

The deeper lesson is about asking the minimum necessary question. Sorting answers "where does every element belong?" — but you only needed to know where one element belongs. Quickselect answers exactly that question and nothing more.

This is a pattern you'll see again and again in algorithm design: the best solution often does less work than the obvious approach, not by being cleverer within the same framework, but by recognizing that the framework itself was overkill.

One loose end: is there a way to guarantee O(n), even with adversarial input? There is — an algorithm called median-of-medians (sometimes called BFPRT, after its five inventors). The idea: instead of picking a random pivot, you deterministically select a pivot that's guaranteed to be “good enough” — within the 30th to 70th percentile. That guarantee means each partition eliminates at least 30% of elements, which keeps the geometric series convergent even in the worst case. The constant factor is large enough that randomized quickselect is faster in practice, but median-of-medians proves that linear-time selection is possible unconditionally — not just in expectation.

Next up: we've been hand-waving about the complexity of these divide-and-conquer algorithms. Time to get precise — and learn to read the shape of a recursion tree.