Quick sort picks a pivot, partitions the array so everything smaller is on the left and everything larger on the right, then recurses on both sides. It sorts in place and is usually the fastest sort in practice — with a worst case that is worth understanding before you trust it.
The idea
After one partition, the pivot is in its final position. Everything left of it is smaller, everything right is larger. Neither side ever needs to look at the other again.
[ 5 3 8 1 9 2 ] pivot = 5
[ 3 1 2 ][5][ 8 9 ] 5 is now permanently correct
\_____/ \__/ recurse into each side independentlyCompare merge sort, which does its work in the combine step. Quick sort does all of it in the divide step, and its combine is nothing at all — which is why it needs no extra array.
Partitioning
int pivot = a[high];
int boundary = low;
for (int i = low; i < high; i++) {
if (a[i] < pivot) {
swap(a, i, boundary++);
}
}
swap(a, boundary, high);
return boundary;This is the Lomuto scheme. boundary marks the end of the "smaller than pivot"
region; anything smaller is swapped into it. One pass, O(n), no extra memory.
⚠️ The worst case is the input you are most likely to get
Quick sort is O(n log n) when the pivot lands near the middle, splitting the array roughly in half. It degrades to O(n²) when the pivot is consistently the smallest or largest element, because then one side holds n−1 elements and the recursion has n levels instead of log n.
With a fixed pivot — always a[high], as in every simple version — that happens on
already-sorted input. Which is not an exotic case: it is what you get from a
database ordered by id, an append-only log, or anything already sorted by something correlated.
The naive quick sort is at its worst on the most ordinary data there is.
// A fixed pivot (always a[high]) makes ALREADY-SORTED input the O(n^2) worst case -
// which is the input you are most likely to be handed. Median-of-three costs three
// comparisons and removes that.
int mid = low + (high - low) / 2;
if (a[mid] < a[low]) {
swap(a, low, mid);
}
if (a[high] < a[low]) {
swap(a, low, high);
}
if (a[high] < a[mid]) {
swap(a, mid, high);
}
swap(a, mid, high);Median-of-three takes the middle value of the first, middle and last elements. On sorted input that is the true median, giving a perfect split. Three comparisons buy immunity to the most common bad case.
It is not a guarantee — an adversary who knows your pivot rule can still construct O(n²) input, which is a real denial-of-service consideration for a server sorting user data. Randomising the pivot removes even that.
⚠️ Bounding the stack
private static void quickSort(int[] a, int low, int high) {
while (low < high) {
int p = partition(a, low, high);
// Recurse into the SMALLER side and loop on the larger. This caps stack depth at
// O(log n) even on input that would otherwise degrade - without it, a sorted array
// plus a bad pivot is a StackOverflowError, not merely a slow sort.
if (p - low < high - p) {
quickSort(a, low, p - 1);
low = p + 1;
} else {
quickSort(a, p + 1, high);
high = p - 1;
}
}
}Two techniques in six lines. Recurse into the smaller side, which is at most half the array, so the depth is at most log₂ n. Then loop on the larger side instead of recursing — a manual tail-call elimination, since Java will not do it for you.
Without this, a degenerate partition means n stack frames: at a million elements the naive version is not slow, it crashes. And this is asserted, not asserted-to-be-true:
// Sorted input used to blow the stack with a fixed pivot. 100k elements proves it does not.
int[] ascending = new int[100_000];
for (int i = 0; i < ascending.length; i++) {
ascending[i] = i;
}
quickSort(ascending);
Check.eq(ascending[0], 0, "100k sorted input does not overflow the stack");Why it beats merge sort in practice
Identical average complexity, but quick sort:
- sorts in place — no O(n) buffer, no copying between arrays;
- partitions sequentially, which is exactly the access pattern caches and prefetchers reward;
- has a smaller constant factor — swapping in place beats copying out and back.
The complexity table says they are equal. The hardware does not.
Not stable
Partitioning swaps elements across the array, so equal elements can end up in either order. That is the one thing merge sort has that this does not, and it is why Java uses quick sort for primitives and merge sort for objects.
What the library actually does
Arrays.sort(int[]) is a dual-pivot quicksort — two pivots, three
partitions — which does fewer swaps on typical data. It also switches to insertion sort on small
subarrays, because insertion sort's tiny constant beats quick sort's below about 44 elements.
Introsort, used in C++ and elsewhere, goes further: it counts recursion depth and switches to heap sort if it goes past ~2·log n. That converts the O(n²) worst case into a guaranteed O(n log n) while keeping quick sort's speed on ordinary input. It is the best of both, and worth naming if someone asks how you would make quick sort safe.
What to remember
- Partition, then recurse — the pivot lands in its final place.
- In place, cache-friendly, usually the fastest in practice.
- O(n²) worst case, and a fixed pivot triggers it on sorted input.
- Median-of-three or a random pivot fixes the common case.
- Recurse into the smaller side and loop on the larger to cap the stack at O(log n).
- Not stable — which is why Java only uses it for primitives.