Interactive Lab · DSA & Algorithms

Sort an array by placing one element at a time, quicksort

Quicksort's whole idea fits in one move: partition. Pick a pivot, sweep the range once shoving everything smaller to its left and everything larger to its right, and the pivot lands in its final sorted position, never to move again. That one placement splits the problem in two. Quickselect stopped here and threw one half away; quicksort keeps both and does the exact same thing to each. Halve, halve, halve until every piece is length 1, and the array is sorted. On average that's O(n log n), in place, no extra array. Scrub through and watch the pivots snap home.

🎬 Watch the 90-second explainer, then sort it yourself below ↓

▶ The playground, partition around a pivot, then sort BOTH sides

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 smaller than the pivot. When the scan ends the pivot swaps to index i, its true sorted spot (it turns green), and both the left and right leftovers go on the to-do stack. Scrub to watch the whole array fall into order.

step 0 / 0

🧭 Where this fits

Quicksort variants sort most of the world's in-memory data: C's qsort, C++'s introsort, and Java's dual-pivot primitive sort are all its descendants. The sorted-input worst case you just triggered is a real historical DoS vector, the reason production sorts randomize pivots or switch to heapsort under adversarial depth.

The code that's actually running, partition, then recurse on both halves

🔮 Predict, then test

Jump to sorted and count: quicksort placed all seven elements with a couple dozen comparisons. Predict: the reason it averages O(n log n) is that a balanced pivot splits the range in half, so you get log n levels of partitioning and each level touches all n elements once, n × log n. But quicksort's pivot here is always the last element. Feed it an already-sorted array and every pivot is the max, so each partition peels off just one element and you get n levels of n work. What's that worst-case cost, and which one-line change to how you pick the pivot makes it vanish?

The takeaway

Your new mental model of quicksort

Partition places one element, exactly. After a partition the pivot sits at its final sorted index, smaller to its left, larger to its right. That element is done forever; you never touch it again.
Recurse into BOTH sides. This is the one difference from quickselect, which kept only the half holding its answer. Quicksort sorts everything, so both halves go back on the to-do list, log n levels deep, n work each → O(n log n) average.
In place, no extra array. All the swapping happens inside the original array, O(log n) stack for the recursion, and that's it. Mergesort is also O(n log n) but needs O(n) scratch space to merge.
Worst case is O(n²), and easily dodged. A bad pivot (always the max/min, e.g. on already-sorted input) peels one element per level → n levels. A random pivot or median-of-three makes that astronomically unlikely; it's why real quicksorts randomize.
Unstable, but fast in practice. Equal elements can swap relative order, so it's not stable. But great cache behavior and low constants make it the default in-memory sort almost everywhere (often as introsort, quicksort that flips to heapsort if recursion goes too deep).

← Quickselect Placement prep →Try: Binary Heap