DSA Sorting
Quick Sort
The query hits at n = 10^7 on a contiguous score array. Cache-local partitions fly... until a bad pivot turns the recursion into a long slide.
Quick sort's engine is . time is Theta(n log n); is Theta(n^2). Typical array forms are and usually unstable.
Algorithm journey
Choose a pivot
Randomize or median-of-three when adversaries matter.
Partition in place
Establish the region invariant with one linear scan.
Pivot is final
Only the two open wings still need work.
Recurse / iterate
Prefer sorting the smaller side first to limit stack.
What actually happens
Naive idea: always pivot on the last element of an already sorted range. Correct answers, Theta(n^2) time.
Better idea: treat partition as the proof step, randomize pivots, and add a depth or heap fallback when balance fails (introsort).
It still fails stability requirements, and duplicate-heavy keys without three-way partitioning can skew badly.
Invariant
During Lomuto partition, indices before the boundary hold keys < pivot; from the boundary through the scan cursor, keys are >= pivot; the pivot sits at the end until placed.
How to choose quick sort
1. Contiguous arrays, stability optional? Tuned quicksort/introsort is a strong default.
2. Need a hard worst-case bound? Heapsort, mergesort, or introsort's heap fallback.
3. Many duplicates? Use three-way (Dutch-national-flag) partitioning.
Quantitative check
Balanced pivots: about 2n ln n comparisons expected. Sorted input with fixed end pivot: about n^2/2 comparisons. At n = 10^6 the gap is millions vs about 5 x 10^11 operations.
Average time
Θ(n log n)
Worst time
Θ(n²)
Auxiliary space
O(log n) expected stack
Properties
In-place · usually unstable
Partition is the algorithm’s engine
Step through a Lomuto partition. Track the region invariant: this is what proves each swap safe and what guarantees the pivot reaches its final rank.
Lomuto partition lab
Follow the boundary, not just the swaps
One pass gives the pivot its final rank. Here B means the inclusive last index below the pivot; the page code stores the equivalent next-free index B + 1.
comparisons
0
swaps
0
unknown
0
unknown
1
unknown
2
unknown
3
unknown
4
pivot
5
Choose the final value 3 as the pivot.
Invariant: Nothing has been scanned yet. The region before the boundary is empty and therefore contains only values < pivot.
less-than region (empty initially)
processed ≥ region (empty initially)
not classified yet
Original interactive quick-sort visualizer (retained)
Use the original full-sort animation to connect repeated partition steps with the array's final order.
The partition invariant
Before the boundary
Every scanned value here is strictly less than the pivot.
Boundary to scan
These values were inspected and are greater than or equal to the pivot.
After the scan
Unclassified values remain, followed by the saved pivot at the end.
When the scan ends, placing the pivot immediately after the less-than region makes every key on its left smaller and every key on its right no smaller. That pivot index is final; only the two open wings still need sorting.
In-place Lomuto implementation
The half-open boundary [lo, boundary) contains keys smaller than the pivot. The partition itself uses O(1) auxiliary storage.
Python
1def partition(a, lo, hi):
2 pivot = a[hi]
3 boundary = lo
4
5 for scan in range(lo, hi):
6 if a[scan] < pivot:
7 a[boundary], a[scan] = a[scan], a[boundary]
8 boundary += 1
9
10 a[boundary], a[hi] = a[hi], a[boundary]
11 return boundary
12
13
14def quick_sort(a, lo=0, hi=None):
15 if hi is None:
16 hi = len(a) - 1
17 if lo >= hi:
18 return
19
20 pivot_index = partition(a, lo, hi)
21 quick_sort(a, lo, pivot_index - 1)
22 quick_sort(a, pivot_index + 1, hi)Java
1final class QuickSort {
2 static void sort(int[] a) {
3 sort(a, 0, a.length - 1);
4 }
5
6 private static void sort(int[] a, int lo, int hi) {
7 if (lo >= hi) return;
8
9 int pivotIndex = partition(a, lo, hi);
10 sort(a, lo, pivotIndex - 1);
11 sort(a, pivotIndex + 1, hi);
12 }
13
14 private static int partition(int[] a, int lo, int hi) {
15 int pivot = a[hi];
16 int boundary = lo;
17
18 for (int scan = lo; scan < hi; scan++) {
19 if (a[scan] < pivot) {
20 swap(a, boundary, scan);
21 boundary++;
22 }
23 }
24
25 swap(a, boundary, hi);
26 return boundary;
27 }
28
29 private static void swap(int[] a, int i, int j) {
30 int temporary = a[i];
31 a[i] = a[j];
32 a[j] = temporary;
33 }
34}This deterministic “last value” pivot is intentionally easy to study, but sorted or reverse-sorted input creates a chain of size n−1, n−2, …. Randomize the pivot or use a guarded hybrid in production.
Where the running time comes from
Balanced splits
T(n) = 2T(n/2) + Θ(n)
There are Θ(log n) levels and Θ(n) partition work per level: Θ(n log n).
Maximally skewed splits
T(n) = T(n−1) + Θ(n)
The work is n + (n−1) + … + 1 = Θ(n²), with an O(n) naive call stack.
Random pivot
Expected Θ(n log n)
For distinct keys, every pivot rank is equally likely, making repeated extreme splits unlikely. Duplicate-heavy inputs still need three-way partitioning to avoid equal-key skew.
A partition of m items always performs Θ(m) comparisons. Balance decides how often elements participate in later partitions. Quick Sort is still a comparison sort, so arbitrary distinct keys retain the Ω(n log n) comparison lower bound in the general case.
Choose a partition scheme deliberately
| Scheme | Shape | Best fit | Watch out for |
|---|---|---|---|
| Lomuto | One scan + one boundary | Simple proof and implementation | More swaps; duplicate-heavy inputs can skew badly |
| Hoare | Pointers move inward | Usually fewer swaps | Return value splits ranges; pivot is not necessarily at its final index |
| Three-way | <, =, and > regions | Many duplicate keys | More boundaries and a slightly richer invariant |
Duplicate keys benefit from a third region
Two-way partitioning may repeatedly recurse over values equal to the pivot. Dutch-national-flag partitioning groups them in one pass, then skips that entire middle block during recursion.
Python
def partition_three_way(a, lo, hi, pivot):
less, scan, greater = lo, lo, hi
while scan <= greater:
if a[scan] < pivot:
a[less], a[scan] = a[scan], a[less]
less += 1
scan += 1
elif a[scan] > pivot:
a[scan], a[greater] = a[greater], a[scan]
greater -= 1 # inspect the incoming value next
else:
scan += 1
return less, greater # equal block is a[less:greater+1]Java
final class ThreeWayPartition {
// Returns {firstEqual, lastEqual}.
static int[] partition(int[] a, int lo, int hi, int pivot) {
int less = lo;
int scan = lo;
int greater = hi;
while (scan <= greater) {
if (a[scan] < pivot) {
swap(a, less++, scan++);
} else if (a[scan] > pivot) {
swap(a, scan, greater--);
// Inspect the incoming a[scan] next.
} else {
scan++;
}
}
return new int[] {less, greater};
}
private static void swap(int[] a, int i, int j) {
int temporary = a[i];
a[i] = a[j];
a[j] = temporary;
}
}Invariant: [lo, less) is smaller, [less, scan) is equal,(greater, hi] is larger, and [scan, greater] is unknown.
Pivot and stack engineering
Random pivot
Swap a uniformly chosen element into the pivot slot. It gives an expected guarantee, not an absolute worst-case guarantee.
Median of three
Use the median of first, middle, and last as a cheap heuristic. It reduces common presorted patterns but remains adversarially breakable.
Smaller side first
Recurse only on the smaller partition and loop over the larger one. The explicit call stack is then bounded by O(log n), even for skewed splits.
Introspective fallback
Track recursion depth and switch to heap sort when it grows too large. Introsort keeps quicksort’s locality with O(n log n) worst-case time.
Insertion cutoff
Small partitions often finish faster with insertion sort because function calls and partition bookkeeping dominate at tiny n.
Cache locality
In-place sequential partition scans contiguous memory, one reason tuned quicksort variants are fast for primitive arrays.
“In-place” still uses a stack
The array partition needs O(1) auxiliary cells, but recursive frames count too: O(log n) expected and O(n) in the naive worst case. Calling Quick Sort simply “O(1) space” hides this distinction.
Why it is usually unstable
Long-distance swaps can reverse equal records. Stable partitioning is possible, but typically needs extra memory or more complex movement, removing a major advantage of conventional Quick Sort.
Correctness and edge-case checklist
- • Empty and one-element ranges must hit the base case.
- • Define whether partition comparisons use
<,≤, or three regions. - • Match recursive bounds to the scheme’s exact return contract.
- • Test all equal, already sorted, reverse sorted, and duplicate-heavy input.
- • Random pivot generation must include every active index uniformly.
- • Never recurse on the pivot index again after Lomuto placement.
Exercises
- Trace Lomuto on
[1,2,3,4]with last-element pivots. How many comparisons across all partitions? - Why does "average Theta(n log n)" not contradict "worst Theta(n^2)"? What distribution is the average over?
- Give a duplicate-heavy array where two-way Lomuto creates empty or tiny wings. What does three-way fix?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): quicksort analysis and randomized pivots.
- Hoare, "Quicksort" (Computer Journal, 1961): original partition scheme.
- Musser, "Introspective Sorting and Selection Algorithms": depth-limited quicksort.
Decision rule
Choose a tuned Quick Sort when contiguous-array locality and low auxiliary allocation matter and stability does not. Add randomized/robust pivots, three-way handling for duplicates, and a depth fallback when an adversarial worst case is unacceptable.