Quick Sort
Pick a pivot, shove smaller left and bigger right, repeat — quicksort is often the fastest sort in practice.
The problem
Merge sort is fast and reliable, but it has a cost you
might not want to pay: it needs a whole second array to merge into. On a huge dataset that
O(n) extra memory hurts, and constantly copying elements between buffers isn't free either.
So here's the question: can you get the same O(n log n) divide-and-conquer speed, but do
all the rearranging in place, inside the original array, with no scratch buffer? That's
the promise of quicksort — and in practice it's often the fastest comparison sort there is.
A first attempt
Merge sort divides blindly at the midpoint and does all its real work combining the halves afterward. That combine step is exactly what forces the extra array.
What if we flip the order of effort? Instead of splitting carelessly and merging carefully, what if we split carefully so that no combining is needed at all? If the left half were guaranteed to hold only small values and the right half only large ones, then sorting each half independently would leave the whole array sorted — nothing to merge.
The insight
Pick one element as the pivot. Rearrange the array so everything smaller than the pivot sits to its left and everything larger sits to its right. Now the pivot is in its final sorted position, and — crucially — the two sides never need to interact again. Recurse into each side.
This rearranging is called partitioning, and it's done with simple swaps inside the same
array: O(1) extra space. The pivot splits the work into two subproblems, giving the same
log n levels as merge sort, but with no buffer and no merge phase.
The pivot is a gamble
Partitioning splits the array into two sides — but not necessarily even sides. A great
pivot halves the array (O(n log n)). A terrible pivot (say, always the largest element on
already-sorted data) peels off one element at a time, giving n levels and O(n²). Pivot
choice is the whole ballgame.
How it works
We'll use Lomuto partitioning: pick the last element as pivot and sweep a boundary of "known-smaller" elements from the left.
Choose a pivot
Take the last element of the current slice as the pivot value.
Sweep and swap smaller elements left
Keep a boundary index i. Scan the slice; every time you find an element < pivot, swap it
into position i and advance i. This packs all smaller elements into the front.
Drop the pivot into place
Swap the pivot into position i. Now everything left of i is smaller and everything right
is larger — the pivot is in its final home.
Recurse on both sides
Quicksort the slice left of the pivot and the slice right of it. Single-element slices are already sorted, ending the recursion.
Partitioning [3, 7, 2, 5] with pivot 5 (the last element), i marks the boundary:
[3 7 2 5] 3 < 5 → swap into i=0, i→1 [3 | 7 2 5]
[3 7 2 5] 7 < 5? no, skip [3 | 7 2 5]
[3 7 2 5] 2 < 5 → swap 2↔7, i→2 [3 2 | 7 5]
place pivot at i=2: swap 5↔7 [3 2 5 7] pivot 5 is home
recurse on [3 2] and [7]The code
def quick_sort(nums, lo=0, hi=None):
if hi is None:
hi = len(nums) - 1
if lo < hi:
p = partition(nums, lo, hi)
quick_sort(nums, lo, p - 1)
quick_sort(nums, p + 1, hi)
return nums
def partition(nums, lo, hi):
pivot = nums[hi]
i = lo
for j in range(lo, hi):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[hi] = nums[hi], nums[i] # pivot into place
return ifunction quickSort(nums: number[], lo = 0, hi = nums.length - 1): number[] {
if (lo < hi) {
const p = partition(nums, lo, hi);
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
}
return nums;
}
function partition(nums: number[], lo: number, hi: number): number {
const pivot = nums[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (nums[j] < pivot) {
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
}
}
[nums[i], nums[hi]] = [nums[hi], nums[i]]; // pivot into place
return i;
}void quickSort(int[] nums, int lo, int hi) {
if (lo < hi) {
int p = partition(nums, lo, hi);
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
}
}
int partition(int[] nums, int lo, int hi) {
int pivot = nums[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) {
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
i++;
}
}
int t = nums[i]; nums[i] = nums[hi]; nums[hi] = t; // pivot into place
return i;
}void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
int partition(int *nums, int lo, int hi) {
int pivot = nums[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) swap(&nums[i++], &nums[j]);
}
swap(&nums[i], &nums[hi]); /* pivot into place */
return i;
}
void quick_sort(int *nums, int lo, int hi) {
if (lo < hi) {
int p = partition(nums, lo, hi);
quick_sort(nums, lo, p - 1);
quick_sort(nums, p + 1, hi);
}
}#include <vector>
#include <utility>
using namespace std;
int partition(vector<int> &nums, int lo, int hi) {
int pivot = nums[hi], i = lo;
for (int j = lo; j < hi; j++) {
if (nums[j] < pivot) swap(nums[i++], nums[j]);
}
swap(nums[i], nums[hi]); // pivot into place
return i;
}
void quickSort(vector<int> &nums, int lo, int hi) {
if (lo < hi) {
int p = partition(nums, lo, hi);
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
}
}Complexity
| Case | Time | Why |
|---|---|---|
| Best | O(n log n) | pivot splits the slice roughly in half |
| Average | O(n log n) | random pivots split well enough on average |
| Worst | O(n²) | pivot is always the min/max — lopsided splits |
| Space | O(log n) | recursion stack (in-place, no data buffer) |
When to use it
The practical default — with one safeguard
Quicksort is usually the fastest in-memory sort thanks to O(1) data space, cache-
friendly sequential access, and tiny constants — which is why it's the default in many
standard libraries. Defuse the O(n²) worst case by choosing the pivot well: pick a
random element, or the median of the first, middle, and last. That makes adversarial
inputs vanishingly unlikely. If you need a hard worst-case guarantee or stability,
reach for merge sort instead — quicksort is not stable.
Practice
Recap
- Quicksort partitions around a pivot so smaller values go left and larger go right, then recurses — all in place with no merge buffer.
- It averages
O(n log n)with excellent constants, but a bad pivot degrades toO(n²); random or median-of-three pivots prevent that. - Prefer it as the fast default; switch to merge sort when you need a worst-case guarantee or stability.
How is this guide?
Last updated on