Algorithms from zero
Quicksort
You know merge sort: divide, sort each half, merge. It is always O(n log n) but uses O(n) extra space. Quicksort is different. It picks a pivot element, rearranges the array so everything smaller is to the left and everything larger is to the right, then recursively sorts the left and right parts. The power of quicksort is speed in practice: it sorts in place (no extra array), is cache-friendly, and on average runs in O(n log n). The catch: if the pivot is chosen badly, quicksort becomes O(n²). Real languages use quicksort (or its variants) because the average case is fast and space is tight.
After this lesson you understand how quicksort works: the partition step (pick a pivot, rearrange so smaller elements are left and larger are right, the pivot ends up in final position), why recursive partition gives O(n log n) on average (balanced partition gives log n levels, each level does O(n) work), why it can be O(n²) in the worst case (unbalanced partitions when the pivot is always the smallest or largest), how to fix the worst case (random pivot or median-of-three), why quicksort is in-place and not stable, and how it compares to merge sort (faster in practice but not stable; merge sort is stable but uses extra space).
The partition step: the heart of quicksort
Quicksort begins with a single key insight: if you can rearrange an array so that a chosen pivot element ends up in its final sorted position, and everything smaller is to the left and everything larger is to the right, then the problem splits into two independent subproblems. Sort the left part and the right part, and you are done.
This rearrangement is called partition. Pick an element as the pivot (often the last element), then walk through the array and swap elements so that:
- All elements < pivot are on the left side.
- The pivot is in its final position.
- All elements > pivot are on the right side.
After partition, the pivot is placed exactly where it belongs in the final sorted array. It will never move again.
Partition in action
Imagine the array [3, 7, 2, 9, 1] with pivot = 1 (the last element).
We want to partition so everything smaller than 1 goes left, 1 goes in the middle, and everything larger goes right. But there is nothing smaller than 1, so the partition result is [1, 7, 2, 9, 3] with pivot at index 0. Now recursively sort the right part [7, 2, 9, 3].
Or consider [3, 7, 2, 9, 5] with pivot = 5:
- Start with two pointers:
iat the left,jat the right (before the pivot). - Scan from left: find the first element ≥ pivot (7 at index 1).
- Scan from right: find the first element < pivot (3 at index 0).
- Swap 7 and 3:
[3, 3, 2, 9, 7](wait, that is index confusion—let me restart with the Lomuto scheme).
The Lomuto partition scheme
A simpler way: maintain a boundary between “smaller” and “larger” regions. Walk through the array once. If an element is smaller than the pivot, move it to the boundary (swap it with the first element in the “larger” region) and advance the boundary.
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1; // pivot's final position
}Walk array [3, 7, 2, 9, 1], pivot = 1:
j=0: arr[0]=3. 3 < 1? No. Skip.j=1: arr[1]=7. 7 < 1? No. Skip.j=2: arr[2]=2. 2 < 1? No. Skip.j=3: arr[3]=9. 9 < 1? No. Skip.- After loop: swap arr[i+1] (arr[0]=3) with arr[high] (arr[4]=1). Result:
[1, 7, 2, 9, 3].
Pivot 1 is now at index 0. Everything to the right (indices 1–4) is larger. Recursively sort [7, 2, 9, 3] (indices 1–4) and [] (indices before 0).
Why O(n log n) on average?
On average, a pivot divides the array roughly in half. That is, partition does O(n) work (one pass), then you recursively sort two halves of roughly equal size. This gives:
- Level 1: O(n) partitioning on the full array.
- Level 2: O(n) partitioning on two halves.
- Level 3: O(n) partitioning on four quarters.
- …
- Level log n: many small partitions, still O(n) total.
Total: log n levels × O(n) work = O(n log n).
The worst case: O(n²)
If the pivot is always the smallest or largest element, partition becomes unbalanced. The left part is empty, and the right part is size n-1. Then:
- Level 1: O(n) partitioning, left one element, right n-1.
- Level 2: O(n-1) partitioning on the right.
- Level 3: O(n-2) partitioning on the right.
- …
- Level n: O(1).
Total: n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n²).
This happens when the array is already sorted (or reverse sorted) and you pick the first or last element as the pivot. This is a real problem.
Fixing the worst case: choose the pivot wisely
- Random pivot: Pick a random element as the pivot. The probability of hitting the worst case repeatedly is exponentially small.
- Median-of-three: Partition on the median of the first, middle, and last elements. This reduces the chance of a bad pivot.
- Introselect: Use quicksort, but if recursion depth exceeds 2 × log n, switch to heapsort to guarantee O(n log n).
Most languages use one of these strategies.
In-place and not stable
Quicksort rearranges the array without allocating a new array. The space used is only the call stack: O(log n) on average (depth of recursion), O(n) in the worst case.
Quicksort is not stable: equal elements may be reordered. If you sort objects by one key and equal values should keep their relative order, quicksort will not preserve it (unlike merge sort).
Quicksort vs merge sort
| Aspect | Quicksort | Merge Sort |
|---|---|---|
| Time (average) | O(n log n) | O(n log n) |
| Time (worst) | O(n²) | O(n log n) |
| Space | O(log n) avg, O(n) worst | O(n) |
| In-place? | Yes | No |
| Stable? | No | Yes |
| Cache-friendly? | Yes | No (random access) |
Quicksort is faster in practice on random data because it is cache-friendly and in-place. Merge sort is predictable and stable. Choose based on your needs.
Let us code quicksort from the ground up.
Step 1: Partition function (Lomuto scheme)
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}This function takes a subarray from index low to high, uses arr[high] as the pivot, and rearranges the subarray so that elements smaller than the pivot are on the left, and elements larger are on the right. It returns the final position of the pivot.
Step 2: Quicksort recursively
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}Partition the array, then recursively sort the left part (indices low to pi - 1) and the right part (indices pi + 1 to high). When low >= high, the subarray has 0 or 1 elements and is already sorted.
Full example
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
const unsorted = [38, 27, 43, 3, 9, 82, 10];
quickSort(unsorted);
console.log("Sorted:", unsorted);Let us run it:
Let us trace partition on the array [3, 7, 2, 9, 1] with pivot = 1 (arr[4]).
1
function partition(arr, low, high) {
2
const pivot = arr[high];
3
let i = low - 1;
4
for (let j = low; j < high; j++) {
5
if (arr[j] < pivot) {
6
i++;
7
[arr[i], arr[j]] = [arr[j], arr[i]];
8
}
9
}
10
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
11
return i + 1;
12
}
This partition placed 1 (the smallest) at index 0. The left part (before 0) is empty, and the right part (indices 1–4) contains [7, 2, 9, 3] and is larger than the pivot. Now recursively quicksort the right part.
| Aspect | Value |
|---|---|
| Time (best case) | O(n log n) |
| Time (average case) | O(n log n) |
| Time (worst case) | O(n²) |
| Space (call stack) | O(log n) avg, O(n) worst |
| Stable? | No |
| In-place? | Yes |
Average case: O(n log n)
On random data, the pivot divides the array roughly in half. This creates log n levels of partitioning, each doing O(n) work, giving O(n log n).
Worst case: O(n²)
If the pivot is always the smallest or largest element, partitions are maximally unbalanced. Only one element is placed correctly per partition step, creating n levels of partitioning, each doing O(n), O(n-1), O(n-2), … = O(n²).
This happens when the array is already sorted and you pick the first or last element. However, on random data or with a good pivot strategy (random, median-of-three), this is unlikely.
Space
Quicksort uses O(log n) space on average (depth of recursion) and O(n) in the worst case. No temporary array is created.
Stability
Quicksort is not stable. Equal elements may be reordered during partition. If stability matters, use merge sort or a stable variant of quicksort (which copies elements into a temporary array, defeating the space advantage).
What does partition do?
When is quicksort worst-case O(n²)?
How does quicksort compare to merge sort in terms of space?
Is quicksort stable?
If an array of 8 elements is partitioned into left size 1 and right size 6 (unbalanced), how many more partitioning levels does this take compared to a balanced partition (4 and 4)?
Common mistake
A quicksort disaster: sorted array with naive pivot. You have a sorted array [1, 2, 3, 4, 5, 6, 7, 8] and use quicksort with pivot = arr[0]. Partition picks 1, moves it to index 0 (already there), and the right part is [2, 3, 4, 5, 6, 7, 8] (size 7). Next, you partition [2, 3, 4, 5, 6, 7, 8] with pivot = 2. Partition picks 2, moves it to index 0 of this subarray, right part is [3, 4, 5, 6, 7, 8] (size 6). This pattern repeats: n, n-1, n-2, …, 1 partitions, each doing O(n) work. Total: O(n²). This is why real implementations use a better pivot strategy—random or median-of-three.
Edge cases
Quicksort on duplicates. Consider [3, 1, 3, 2, 3]. With quicksort (Lomuto partition), the pivot 3 may end up anywhere among the duplicates. Subsequent partitions will reorder the three 3’s relative to each other. This is why quicksort is not stable. If you need stability, use merge sort or a variant that groups equal elements together before recursing.
You are designing a real-time system that must sort user IDs. Speed matters most, and memory is limited. The input is random (not sorted or nearly sorted). Should you use quicksort or merge sort?
Quicksort picks a pivot, partitions the array so the pivot is in its final position, then recursively sorts the left and right parts.
Partition rearranges the array: walk through, swap elements so smaller ones are left of the pivot and larger are right. The pivot ends up in its final sorted position.
Time complexity: O(n log n) on average (balanced partitions give log n levels, each doing O(n) work). O(n²) worst case if the pivot is always the smallest or largest (happens on sorted input with naive pivot choice).
Space: O(log n) average (recursion depth), O(n) worst case. No extra array.
In-place: Yes. The array is rearranged without allocating a new one.
Stable: No. Equal elements may be reordered during partition.
vs Merge sort: Quicksort is faster in practice (cache-friendly, less space), but merge sort is stable and has a guaranteed O(n log n). Choose based on whether stability or worst-case performance matters.
Why learn it? Quicksort is the default sorting algorithm in most languages because it is fast in practice. Understanding how partition works teaches you in-place manipulation and why pivot choice matters for performance.