Quicksort

By Victor Arce

Quicksort is the other great divide and conquerDivide and conquer: solve a problem by splitting it into subproblems, solving each, then combining the results. sort — but where merge sort splits down the middle and does its work while merging back up, quicksort does its work on the way down, while splitting. It picks one value as a pivot, partitions the rest so that everything smaller sits to its left and everything larger to its right, and then sorts each side the same way. The pivot lands in its final place immediately, and no merge step is needed.

Step through it below. Each comparison to the pivot is a step; the pivot is the highlighted cell, and the → marks the value being compared. Toggle show log to follow along in words.

How it works

For each run we take the last element as the pivot, then walk the rest left to right keeping a boundary: everything before the boundary is already known to be smaller than the pivot. Each value we meet that is smaller than the pivot is swapped to the boundary and the boundary moves right. When the scan finishes, we drop the pivot just past the boundary — now everything to its left is smaller and everything to its right is larger, so the pivot is in its final sorted position.

That single placement splits the run into two smaller runs. We recurse into each; a run of one element is already sorted. Once both sides are done the whole range is sorted — there is nothing to combine.

Cost

On average quicksort runs in O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts.: each level of partitioning touches all n values once, and good pivots halve the run each time (about log n levels). Its worst case is O(n²) — already-sorted input with a last-element pivot makes every partition lopsided — which real implementations avoid by choosing the pivot smarter (median-of-three, or random). It sorts in-placeIn-place: sorts within the original array using only a little extra memory (no second array). (only a little stack space) but is not stableStable: equal values keep their original relative order after sorting. by default, since partitioning can reorder equal values. In practice its tight inner loop makes it one of the fastest comparison sorts, and it's a common choice in standard libraries.

Back to Sorting Algorithms