Interactive Lab · DSA & Algorithms

Find the k-th largest without sorting the whole thing, quickselect

“What's the 3rd largest number?” You could sort everything and read off the answer, that's O(n log n). But you don't need the whole order, just one element. Quickselect gets it in O(n) on average by borrowing quicksort's partition: pick a pivot, shove the bigger values to its left and the smaller to its right, and the pivot snaps into its final sorted position. Now you know exactly which half the answer is in, so you throw the other half away and repeat. Half the work vanishes every round. Watch it hunt down the 3rd largest.

🎬 Watch the 90-second explainer, then hunt the k-th largest yourself below ↓

▶ The playground, partition around a pivot, then recurse into just one side

Each bar is a number. The pivot is the last bar of the live range; we scan with j and keep a boundary i for values bigger than the pivot. When the scan ends, the pivot swaps to index iits true sorted spot. The ▼ target is index k−1; if the pivot lands there we're done, otherwise the greyed half is discarded. Scrub to watch.

step 0 / 0

🧭 Where this fits

Quickselect finds medians and percentiles without sorting: p99 latency computation in monitoring pipelines, median-of-column in query engines, and top-K selection all use it (C++'s nth_element IS quickselect). The O(n)-average/O(n²)-worst story you just traced is a top-5 interview question because it tests pivot reasoning.

The code that's actually running, partition, then recurse one side

🔮 Predict, then test

Jump to the answer: the 3rd largest is 7, and quickselect found it after just a handful of comparisons, never fully sorting. Predict: the reason it's O(n) on average is that it recurses into only one half, so the work is n + n/2 + n/4 + … ≈ 2n, versus quicksort touching both halves for O(n log n). But there's a catch, if the pivot is always the largest or smallest, you peel off just one element per round. What's the worst-case cost then, and what simple pivot trick makes the bad case vanishingly unlikely?

The takeaway

Your new mental model of quickselect

Selection, not sorting. You want one order statistic, the k-th element, not the whole ranking. Sorting does far more work than the question asks for.
Partition places one element exactly. After a partition, the pivot sits at its final sorted index, everything bigger to one side, smaller to the other. That single fact tells you which half holds your answer.
Recurse into ONE side. Quicksort recurses into both halves (O(n log n)); quickselect recurses into just the half that can contain index k−1. Halving each round sums to ≈ 2n → O(n) average.
Worst case is O(n²), and easily dodged. A pathologically bad pivot (always the max/min) peels one element per round. A random pivot (or median-of-medians) makes that astronomically unlikely / guarantees O(n).
When to reach for it: medians, percentiles, and “top-k” when you don't need the top-k sorted. If you do want them ordered, or k is tiny, a size-k heap (O(n log k)) is the other classic answer.

← Binary Heap Placement prep →Try: Binary Search