Where it runs
1. The problem
Merge sort gave you O(n log n) time. It cuts the list in half without looking at the values. It does most of its work later, when it merges the halves. Another method reaches the same speed: it does most of the work before the split.
Pick one item and call it the pivot. Split the others into two groups: the numbers smaller than the pivot and the numbers not smaller than it. Now the pivot is in its final place: everything on its left is smaller, everything on its right is equal or bigger. You never have to move it again.
That one move is the whole idea. Make it, then make the same move in each group.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- sort an array of real size (thousands+)
- need O(n log n) guaranteed or expected
- sort as a subroutine before another algorithm (two pointers, greedy, sweep)
- stability required (merge sort) or in-place expected (quicksort)
- just "sort this" with no small-n or special-key hint
Looks similar, isn't
- Elementary sorts (selection, bubble, insertion)
Those never split the array and cost n squared. Splitting is what buys the log n.
- Non-comparison sort (counting / radix)
Counting and radix sort beat n log n by reading digits. They need keys in a small range.
- Binary heap / priority queue
Heap sort also runs in n log n and needs no buffer. It is slower in practice on real data.
- Recursion
Recursion is the mechanism these use, not the pattern. Where the cut goes is the real idea.
n up to 1e6 gives O(n log n). Merge sort needs O(n) extra memory, quick sort needs O(log n).
On LeetCode
Problems that split an array around a pivot value, or find the kth largest item without sorting everything. One partition puts the pivot in its final place.
The lesson's partition with an extra group for values equal to the pivot, each group in its original order.
One partition, with "is even" in place of "is smaller than the pivot".
Partition, then go on only in the side that holds position k, which is how quickselect works.
Take a random pivot and a separate group for equal values, because the last-item pivot is too slow on the tests full of repeats.