Quicksort
Medium+90 XPPick a pivot, push smaller values left and bigger ones right, then repeat on each side. O(n log n) on average.
No visualization loaded.
Watch
—
Press Run to begin.
Quicksort works by picking one value — the 'pivot' — and then shoving every smaller value to its left and every bigger value to its right. Once that's done, the pivot is sitting in its FINAL spot (everyone on the left is smaller, everyone on the right is bigger). Now you do the exact same trick on the left chunk and the right chunk, and on their chunks, until every piece is size one and the whole array is sorted. It's divide-and-conquer, but instead of splitting in the middle like merge sort, you split around a pivot.
▸What's a pivot?
Just one value you choose from the range to be the 'fence post.' Everything smaller goes on its left, everything bigger goes on its right. After that one pass, the pivot is locked into its correct final position and never moves again. You can pick any element as the pivot — the front, the back, the middle, or even a random one.
▸What does 'partitioning' mean?
It's the one-pass shuffle that splits a range into 'smaller than the pivot' and 'bigger than the pivot.' You sweep across the range comparing each value to the pivot; smaller values get swapped to the left side. At the end you drop the pivot right between the two groups. That single sweep is O(n) work, and it's the heart of quicksort.
▸Why is it usually O(n log n) but O(n²) in the worst case?
Each partition is O(n) work. If the pivot lands roughly in the MIDDLE each time, you halve the range about log n times — n × log n total, fast. But if you keep picking a terrible pivot (say, always the smallest value, which happens on an already-sorted array with this scheme), one side is empty and you only peel off one element per pass — that's n levels of O(n) work = O(n²). Picking a random or middle pivot makes the bad case extremely unlikely.
▸Why is it 'in-place' and so fast in practice?
It sorts by swapping elements within the same array, so it needs almost no extra memory — just a little stack space for the recursion, O(log n). And because all that swapping happens in nearby slots, it plays nicely with how real computers fetch memory (good 'cache' behavior). That low overhead is why quicksort is often the fastest sort in real life, even though merge sort has the same O(n log n) class.
How the work grows
O(n log n) average, O(n²) worst is good — the practical sorting speed. Each partition is O(n). Good pivots split the range in half about log n times → n×log n. Unlucky pivots peel off one element at a time → n levels → O(n²). It sorts inside the same array, so the only extra memory is the recursion stack, ~log n deep.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.