Quick Sort
What Is Quick Sort?
Quick sort selects a pivot element, partitions the array so that all smaller elements are to the left and all larger elements are to the right, then recursively sorts the two partitions.
Array: [3, 6, 8, 10, 1, 2, 1] Pivot = 3 (last element)
Partition: everything ≤ 3 goes left, everything > 3 goes right
[1, 2, 1, 3, 6, 8, 10]
↑
Pivot in final position
Recurse left: [1, 2, 1] → sort to [1, 1, 2]
Recurse right: [6, 8, 10] → already sorted
Result: [1, 1, 2, 3, 6, 8, 10] ✓
The pivot's final position is determined after partitioning. Once placed, the pivot never moves again. This is the key insight: each recursive call reduces the problem by at least one element (the pivot).
Partition Scheme 1: Lomuto
Lomuto partition moves a single pointer j through the array. Elements ≤ pivot are moved to the left side as j advances. The pivot starts at arr[hi] and is placed at its final position at the end.
Lomuto partition of [3, 6, 8, 10, 1, 2, 1], lo=0, hi=6, pivot=arr[6]=1 i = lo - 1 = -1 (boundary: arr[0..i] ≤ pivot) j=0: arr[0]=3 > 1 → skip j=1: arr[1]=6 > 1 → skip j=2: arr[2]=8 > 1 → skip j=3: arr[3]=10 > 1 → skip j=4: arr[4]=1 ≤ 1 → i++, swap arr[0] and arr[4] [1,6,8,10,3,2,1] j=5: arr[5]=2 > 1 → skip j=6: done. Place pivot: i++, swap arr[1] and arr[6] → final pivot at index 1 Wait — let's redo with correct logic: i=-1, j starts 0, pivot = arr[hi=6] = 1 j=0: arr[0]=3 > pivot=1 → no swap j=1: arr[1]=6 > 1 → no swap j=2: arr[2]=8 > 1 → no swap j=3: arr[3]=10 > 1 → no swap j=4: arr[4]=1 ≤ 1 → i++=-1+1=0, swap arr[0]↔arr[4]: [1,6,8,10,3,2,1] j=5: arr[5]=2 > 1 → no swap End: i+1=1, swap arr[1]↔arr[6]: [1,1,8,10,3,2,6] pivot at index 1 ✓ Left partition: [1] (index 0) Right partition: [8,10,3,2,6] (indices 2..6)
1public class QuickSortLomuto {
2
3 // Lomuto partition — pivot = arr[hi]
4 private static int partition(int[] arr, int lo, int hi) {
5 int pivot = arr[hi];
6 int i = lo - 1; // i: rightmost index of "≤ pivot" region
7
8 for (int j = lo; j < hi; j++) {
9 if (arr[j] <= pivot) {
10 i++;
11 // Swap arr[i] and arr[j]
12 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
13 }
14 }
15
16 // Place pivot at position i+1
17 i++;
18 int tmp = arr[i]; arr[i] = arr[hi]; arr[hi] = tmp;
19 return i; // Pivot's final index
20 }
21
22 public static void quickSort(int[] arr, int lo, int hi) {
23 if (lo >= hi) return; // Base case: 0 or 1 elements
24
25 int pivotIdx = partition(arr, lo, hi);
26 quickSort(arr, lo, pivotIdx - 1); // Sort left of pivot
27 quickSort(arr, pivotIdx + 1, hi); // Sort right of pivot
28 }
29
30 public static void sort(int[] arr) {
31 if (arr.length > 1) quickSort(arr, 0, arr.length - 1);
32 }
33
34 public static void main(String[] args) {
35 int[] arr1 = {10, 7, 8, 9, 1, 5};
36 sort(arr1);
37 System.out.println(java.util.Arrays.toString(arr1));
38 // [1, 5, 7, 8, 9, 10]
39
40 int[] arr2 = {64, 34, 25, 12, 22, 11, 90};
41 sort(arr2);
42 System.out.println(java.util.Arrays.toString(arr2));
43 // [11, 12, 22, 25, 34, 64, 90]
44 }
45}Output:
[1, 5, 7, 8, 9, 10]
[11, 12, 22, 25, 34, 64, 90]
Dry Run: Lomuto on [10, 7, 8, 9, 1, 5]
lo=0, hi=5, pivot=arr[5]=5, i=-1
j=0: arr[0]=10 > 5 → skip
j=1: arr[1]=7 > 5 → skip
j=2: arr[2]=8 > 5 → skip
j=3: arr[3]=9 > 5 → skip
j=4: arr[4]=1 ≤ 5 → i=0, swap arr[0]↔arr[4]: [1,7,8,9,10,5]
End: swap arr[i+1=1]↔arr[hi=5]: [1,5,8,9,10,7] pivot at index 1 ✓
Recurse left: [1] → base case
Recurse right: [8,9,10,7]
lo=2, hi=5, pivot=arr[5]=7, i=1
j=2: 8>7 → skip
j=3: 9>7 → skip
j=4: 10>7 → skip
swap arr[2]↔arr[5]: [1,5,7,9,10,8] pivot at index 2
Recurse left: [] → base case
Recurse right: [9,10,8]
lo=3, hi=5, pivot=8, i=2
j=3: 9>8 → skip
j=4: 10>8 → skip
swap arr[3]↔arr[5]: [1,5,7,8,10,9] pivot at index 3
Recurse left: [] → base case
Recurse right: [10,9]
pivot=9, 10>9 → 9 at index 4
[1,5,7,8,9,10] ✓
Partition Scheme 2: Hoare
Hoare's scheme uses two pointers starting at opposite ends, moving inward until they find a pair that is out of place, then swapping them. It does fewer swaps on average than Lomuto.
Critical difference: After Hoare's partition, the pivot is not necessarily at the returned index p. The invariant is: arr[lo..p] ≤ pivot and arr[p+1..hi] ≥ pivot. The recursive calls must be quickSort(lo, p) and quickSort(p+1, hi) — not p-1 and p+1.
1public class QuickSortHoare {
2
3 // Hoare partition — pivot = arr[lo] (first element)
4 private static int partitionHoare(int[] arr, int lo, int hi) {
5 int pivot = arr[lo]; // Pivot is first element
6 int i = lo - 1;
7 int j = hi + 1;
8
9 while (true) {
10 do { i++; } while (arr[i] < pivot); // Move i right until arr[i] >= pivot
11 do { j--; } while (arr[j] > pivot); // Move j left until arr[j] <= pivot
12
13 if (i >= j) return j; // Pointers crossed — partition complete
14
15 // arr[i] is too large (≥ pivot on right side) and
16 // arr[j] is too small (≤ pivot on left side) — swap them
17 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
18 }
19 }
20
21 public static void quickSortHoare(int[] arr, int lo, int hi) {
22 if (lo >= hi) return;
23
24 int p = partitionHoare(arr, lo, hi);
25 quickSortHoare(arr, lo, p); // Note: lo..p (not lo..p-1)
26 quickSortHoare(arr, p + 1, hi);
27 }
28
29 public static void sort(int[] arr) {
30 if (arr.length > 1) quickSortHoare(arr, 0, arr.length - 1);
31 }
32
33 public static void main(String[] args) {
34 int[] arr1 = {10, 7, 8, 9, 1, 5};
35 sort(arr1);
36 System.out.println(java.util.Arrays.toString(arr1));
37 // [1, 5, 7, 8, 9, 10]
38
39 int[] arr2 = {3, 6, 8, 10, 1, 2, 1};
40 sort(arr2);
41 System.out.println(java.util.Arrays.toString(arr2));
42 // [1, 1, 2, 3, 6, 8, 10]
43 }
44}Output:
[1, 5, 7, 8, 9, 10]
[1, 1, 2, 3, 6, 8, 10]
Dry Run: Hoare on [8, 3, 1, 7, 0, 10, 2]
lo=0, hi=6, pivot=arr[0]=8
i=-1, j=7
Move i right (arr[i] < 8): i=0 (arr[0]=8 ≥ 8 → stop)
Move j left (arr[j] > 8): j=6 (arr[6]=2 ≤ 8 → stop)
i=0 < j=6 → swap arr[0]↔arr[6]: [2,3,1,7,0,10,8]
Move i right: i=1(3<8), i=2(1<8), i=3(7<8), i=4(0<8), i=5(10≥8 → stop)
Move j left: j=5(10>8), j=4(0≤8 → stop)
i=5 > j=4 → STOP, return j=4
Recurse left: quickSort([2,3,1,7,0], lo=0, hi=4)
Recurse right: quickSort([10,8], lo=5, hi=6)
Note: pivot=8 is at index 6 (moved there by first swap),
NOT at the returned index 4. Hoare's return value is NOT the pivot index.
Randomised Quick Sort
Randomly select the pivot before each partition. Eliminates adversarial worst-case inputs — expected O(n log n) regardless of input order.
1import java.util.Random;
2
3public class RandomisedQuickSort {
4
5 private static final Random rand = new Random();
6
7 private static int partition(int[] arr, int lo, int hi) {
8 // Random pivot: swap a random element with arr[hi], then use Lomuto
9 int pivotIdx = lo + rand.nextInt(hi - lo + 1);
10 int tmp = arr[pivotIdx]; arr[pivotIdx] = arr[hi]; arr[hi] = tmp;
11
12 int pivot = arr[hi], i = lo - 1;
13 for (int j = lo; j < hi; j++) {
14 if (arr[j] <= pivot) {
15 i++;
16 tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
17 }
18 }
19 tmp = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = tmp;
20 return i + 1;
21 }
22
23 public static void quickSort(int[] arr, int lo, int hi) {
24 if (lo >= hi) return;
25 int p = partition(arr, lo, hi);
26 quickSort(arr, lo, p - 1);
27 quickSort(arr, p + 1, hi);
28 }
29
30 public static void main(String[] args) {
31 // Already sorted — worst case for last-element pivot, but fine for random pivot
32 int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
33 quickSort(arr, 0, arr.length - 1);
34 System.out.println(java.util.Arrays.toString(arr));
35 // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
36 }
37}Three-Way Partition (Dutch National Flag)
When the array has many duplicate elements, standard quick sort degrades — all duplicates end up on the same side and the pivot region is repeatedly re-processed. Three-way partition places all equal-to-pivot elements in their final positions in one pass, then only recursively sorts the < pivot and > pivot regions.
Array: [2, 1, 2, 3, 2, 0, 2] pivot = 2 Three-way partition result: [0, 1, | 2, 2, 2, 2, | 3] lt=2 eq=2..5 gt=6 All 2s are now in their final positions — never touched again. Recurse only on [0,1] and [3]. Without three-way: the pivot (2) is placed in one position, and all other 2s must be re-processed in both recursive calls — O(n²) for an array of all equal elements. With three-way: O(n) for an array of all equal elements — one pass.
1public class ThreeWayQuickSort {
2
3 // Dutch National Flag partition
4 // Returns [lt, gt]: arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
5 private static int[] threeWayPartition(int[] arr, int lo, int hi) {
6 int pivot = arr[lo];
7 int lt = lo; // arr[lo..lt-1] < pivot
8 int gt = hi; // arr[gt+1..hi] > pivot
9 int i = lo; // current element
10
11 while (i <= gt) {
12 if (arr[i] < pivot) {
13 int tmp = arr[lt]; arr[lt] = arr[i]; arr[i] = tmp;
14 lt++; i++;
15 } else if (arr[i] > pivot) {
16 int tmp = arr[gt]; arr[gt] = arr[i]; arr[i] = tmp;
17 gt--; // Don't increment i — newly placed element at i is unexamined
18 } else {
19 i++; // arr[i] == pivot — already in correct region
20 }
21 }
22
23 return new int[]{lt, gt};
24 }
25
26 public static void quickSort3Way(int[] arr, int lo, int hi) {
27 if (lo >= hi) return;
28
29 int[] bounds = threeWayPartition(arr, lo, hi);
30 int lt = bounds[0];
31 int gt = bounds[1];
32
33 quickSort3Way(arr, lo, lt - 1); // Sort < pivot region
34 quickSort3Way(arr, gt + 1, hi); // Sort > pivot region
35 // [lt..gt] region (all == pivot) is already sorted — skip
36 }
37
38 public static void main(String[] args) {
39 int[] arr1 = {2, 1, 2, 3, 2, 0, 2};
40 quickSort3Way(arr1, 0, arr1.length - 1);
41 System.out.println(java.util.Arrays.toString(arr1));
42 // [0, 1, 2, 2, 2, 2, 3]
43
44 // Array of all equal elements — O(n) with 3-way, O(n²) without
45 int[] arr2 = {5, 5, 5, 5, 5};
46 quickSort3Way(arr2, 0, arr2.length - 1);
47 System.out.println(java.util.Arrays.toString(arr2));
48 // [5, 5, 5, 5, 5]
49 }
50}Output:
[0, 1, 2, 2, 2, 2, 3]
[5, 5, 5, 5, 5]
Dry Run: Three-Way Partition on [2, 1, 2, 3, 2, 0, 2]
lo=0, hi=6, pivot=2, lt=0, i=0, gt=6
i=0: arr[0]=2 == 2 → i=1
i=1: arr[1]=1 < 2 → swap arr[lt=0]↔arr[i=1]: [1,2,2,3,2,0,2], lt=1, i=2
i=2: arr[2]=2 == 2 → i=3
i=3: arr[3]=3 > 2 → swap arr[i=3]↔arr[gt=6]: [1,2,2,2,2,0,3], gt=5
i=3: arr[3]=2 == 2 → i=4
i=4: arr[4]=2 == 2 → i=5
i=5: arr[5]=0 < 2 → swap arr[lt=1]↔arr[i=5]: [1,0,2,2,2,2,3], lt=2, i=6
i=6 > gt=5 → STOP
lt=2, gt=5
arr = [1, 0, | 2, 2, 2, 2 | 3]
lt=2 to gt=5
Recurse left: [1, 0] (lo=0, hi=1)
Recurse right: [3] (lo=6, hi=6 — base case)
Middle [2,2,2,2] is fully in final positions — never touched again ✓
Pivot Selection Strategies
Strategy Pros Cons
──────────────────────────────────────────────────────────────────
Last element (arr[hi]) Simple implementation O(n²) on sorted/reverse-sorted
First element (arr[lo]) Simple implementation O(n²) on sorted/reverse-sorted
Middle element (arr[mid])Better for sorted input Still O(n²) for some inputs
Median-of-three Practical best pivot Slightly more complex
(median of lo,mid,hi)
Random pivot O(n log n) expected Needs random number generation
— no adversarial input
Median-of-three implementation:
candidates = arr[lo], arr[mid], arr[hi]
pivot = median of these three
Code:
int mid = lo + (hi - lo) / 2;
if (arr[lo] > arr[mid]) swap(arr[lo], arr[mid]);
if (arr[lo] > arr[hi]) swap(arr[lo], arr[hi]);
if (arr[mid] > arr[hi]) swap(arr[mid], arr[hi]);
// Now arr[lo] ≤ arr[mid] ≤ arr[hi]
// Median is at arr[mid] — move to arr[hi] for Lomuto
Benefits:
- Always avoids O(n²) for already-sorted, reverse-sorted, and constant arrays
- Slightly slower per pivot selection, much faster overall for real data
Iterative Quick Sort
Replace recursion with an explicit stack to avoid stack overflow for deeply recursive calls.
1import java.util.Deque;
2import java.util.ArrayDeque;
3
4public class IterativeQuickSort {
5
6 private static int partition(int[] arr, int lo, int hi) {
7 int pivot = arr[hi], i = lo - 1;
8 for (int j = lo; j < hi; j++) {
9 if (arr[j] <= pivot) { i++; int t=arr[i]; arr[i]=arr[j]; arr[j]=t; }
10 }
11 int t = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = t;
12 return i + 1;
13 }
14
15 public static void iterativeQuickSort(int[] arr) {
16 int n = arr.length;
17 if (n <= 1) return;
18
19 Deque<Integer> stack = new ArrayDeque<>();
20 stack.push(0);
21 stack.push(n - 1);
22
23 while (!stack.isEmpty()) {
24 int hi = stack.pop();
25 int lo = stack.pop();
26
27 if (lo >= hi) continue;
28
29 int p = partition(arr, lo, hi);
30
31 // Push smaller subarray first (tail recursion optimisation)
32 // ensures stack depth is O(log n) in the worst case
33 if (p - 1 - lo < hi - (p + 1)) {
34 stack.push(lo); stack.push(p - 1); // Left
35 stack.push(p + 1); stack.push(hi); // Right
36 } else {
37 stack.push(p + 1); stack.push(hi); // Right
38 stack.push(lo); stack.push(p - 1); // Left
39 }
40 }
41 }
42
43 public static void main(String[] args) {
44 int[] arr = {10, 7, 8, 9, 1, 5};
45 iterativeQuickSort(arr);
46 System.out.println(java.util.Arrays.toString(arr));
47 // [1, 5, 7, 8, 9, 10]
48 }
49}Lomuto vs Hoare Comparison
Property Lomuto Hoare ────────────────────────────────────────────────────────────────── Pivot position arr[hi] arr[lo] Pivot in final position? ✓ Yes (at return p) ✗ No (p is boundary, not pivot) Recursive call bounds (lo,p-1),(p+1,hi) (lo,p),(p+1,hi) Average swaps ~n/2 ~n/3 ← fewer Code complexity Simpler Slightly more complex Works with duplicates Yes (≤ condition) Yes Stable? ✗ No ✗ No
Complexity Summary
| Variant | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Lomuto (last pivot) | O(n log n) | O(n log n) | O(n²) sorted/reverse | O(log n) | ✗ No |
| Hoare (first pivot) | O(n log n) | O(n log n) | O(n²) sorted/reverse | O(log n) | ✗ No |
| Random pivot | O(n log n) | O(n log n) | O(n²) with probability 1/n! | O(log n) | ✗ No |
| Three-way + random | O(n) all equal | O(n log n) | O(n log n) expected | O(log n) | ✗ No |
| Iterative | O(n log n) | O(n log n) | O(n²) comparisons | O(log n) stack | ✗ No |
Common Mistakes
Using quickSort(arr, lo, p) instead of quickSort(arr, lo, p-1) with Lomuto. Lomuto guarantees the pivot is at index p after partition. The left recursion must sort arr[lo..p-1] (excluding the pivot). Using (lo, p) re-processes the pivot, causing infinite recursion when the pivot is at lo.
Using quickSort(arr, lo, p-1) instead of quickSort(arr, lo, p) with Hoare. The opposite error. Hoare's p is NOT the pivot position — it is the boundary. Excluding p from the left recursion can leave arr[p] unsorted. Always use (lo, p) and (p+1, hi) with Hoare.
Not incrementing i after a > pivot swap in three-way partition. When arr[i] > pivot, swap with arr[gt] and decrement gt — but do NOT increment i. The element moved from arr[gt] to arr[i] is unexamined and may itself be less than, equal to, or greater than the pivot. Incrementing i skips this element, potentially placing it in the wrong region.
Always choosing the last element as pivot on already-sorted input. For sorted input with last-element pivot, every partition step produces one empty sub-array and one of size n-1 — O(n²) recursion depth and O(n²) comparisons. Always use random pivot or median-of-three in production.
Interview Questions
Q: What is the worst case of quick sort and how do you avoid it?
O(n²) occurs when every pivot chosen is the minimum or maximum of its subarray, creating unbalanced partitions of size 1 and n-1. With n recursive calls each costing O(n), total is O(n²). This happens naturally with last-element pivot on already-sorted or reverse-sorted input. Fixes: (1) random pivot — expected O(n log n) with probability of O(n²) being 1/n!; (2) median-of-three — avoids O(n²) for sorted, reverse-sorted, and constant input.
Q: Why is quick sort generally faster than merge sort in practice despite the same O(n log n) complexity?
Quick sort is in-place — it works directly on the original array with only O(log n) stack space. Merge sort allocates O(n) extra memory for the auxiliary array. Quick sort's partition step accesses elements sequentially within a contiguous array segment — excellent cache locality. Merge sort's merge step reads from two separate regions and writes to a third, causing more cache misses. The constant factors in quick sort's O(n log n) are smaller in practice.
Q: How does three-way partitioning improve performance for arrays with duplicates?
Standard quick sort places only one pivot in its final position per recursive call. If many elements equal the pivot, they are distributed to both left and right sub-arrays and re-processed repeatedly — O(n²) for an all-equal array. Three-way partition places ALL equal-to-pivot elements in their final positions in one pass, then recurses only on < pivot and > pivot regions. For an all-equal array, one partition step is O(n) and there are no recursive calls — O(n) total.
FAQs
Is quick sort stable?
No — neither Lomuto nor Hoare scheme is stable. The partition step can move elements long distances, reversing equal elements. If stability is required, use merge sort or TimSort instead.
What is introsort and why is it used in C++ std::sort?
Introsort (introspective sort) is a hybrid algorithm: it starts with quick sort but monitors the recursion depth. When the depth exceeds 2 × log(n) (indicating an unbalanced partition), it switches to heap sort to guarantee O(n log n) worst case. For small subarrays it uses insertion sort. This gives quick sort's average-case speed without the O(n²) worst-case risk.
Can quick sort be parallelised?
Yes — after each partition, the two sub-arrays are completely independent and can be sorted in parallel. This is a natural fork-join parallel algorithm. In practice, parallel quick sort is competitive for large arrays on multicore hardware, spawning threads for sub-arrays above a size threshold and falling back to sequential sort for small sub-arrays.
Summary
Quick sort partitions around a pivot element, placing it in its final position, then recursively sorts both sides.
Two partition schemes:
- ›Lomuto — simpler, one pointer forward; pivot ends at returned index
p; recurse(lo, p-1)and(p+1, hi) - ›Hoare — faster (~n/3 swaps vs ~n/2); two inward pointers; pivot NOT at returned index
p; recurse(lo, p)and(p+1, hi)
Pivot strategies:
- ›Last element — simple, O(n²) on sorted input
- ›Random — expected O(n log n) for all inputs
- ›Median-of-three — practical best, avoids common O(n²) cases
Three-way partition (Dutch National Flag):
- ›Produces
[< pivot | == pivot | > pivot]regions - ›All equal-to-pivot elements placed in final positions in one pass
- ›Essential for arrays with many duplicates — O(n log n) where standard is O(n²)
Complexity:
- ›Average: O(n log n) — Worst: O(n²) with bad pivot
- ›Space: O(log n) average, O(n) worst (recursion stack)
- ›Not stable — long-distance swaps break equal element order
In the next topic, you will explore Stable vs Unstable Sorting — a deep dive into when stability matters, how to test for it, and which algorithms guarantee it.
What is the average-case time complexity of quick sort?