Topics › Sorting › Sorting-II

Quick Sorting

Easy TUF ID 946 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using quick sort: choose a pivot element, rearrange the array so that everything smaller than or equal to the pivot is on its left and everything larger is on its right (the pivot is then at its final position), and recursively sort the two sides.

Constraints: 1 ≤ n ≤ 10^5, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed.

Example 1

arr = [4, 6, 2, 5, 7, 9, 1, 3]
answer = [1, 2, 3, 4, 5, 6, 7, 9]     // after partitioning around 4: [1, 3, 2, 4, 7, 9, 5, 6]

Example 2

arr = [5, 4, 4, 1, 1]
answer = [1, 1, 4, 4, 5]              // duplicates must not break the partition

Approach 1: Pivot at the front, two pointers walking inward

Intuition. Merge sort does all its work after the recursive calls, in the merge. Quick sort does all its work before them, in the partition. If we can place one element, the pivot, at the index it will occupy in the sorted array, with every smaller-or-equal element somewhere to its left and every larger element somewhere to its right, then the two sides can be sorted independently and nothing ever needs to be merged.

The partition in the A2Z sheet picks arr[low] as the pivot and uses two pointers. i walks right from low looking for an element greater than the pivot (one that is on the wrong side). j walks left from high looking for an element less than or equal to the pivot. When both have stopped and i < j, the two elements are each on the wrong side, so swapping them fixes both. When the pointers cross, j is the last index holding a value <= pivot; swapping the pivot from low into j puts it exactly between the small and the large elements.

Algorithm.

1. quickSort(arr, low, high): if low >= high return (zero or one element).
2. p = partition(arr, low, high); recurse on [low, p - 1] and [p + 1, high].
3. partition: pivot = arr[low], i = low, j = high. While i < j: advance i while arr[i] <= pivot (and i < high); retreat j while arr[j] > pivot (and j > low); if i < j swap arr[i] and arr[j].
4. Swap arr[low] with arr[j] and return j.

static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int p = partition(arr, low, high);
    quickSort(arr, low, p - 1);
    quickSort(arr, p + 1, high);
}

static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low, j = high;
    while (i < j) {
        while (i <= high - 1 && arr[i] <= pivot) i++;   // first element from the left that is > pivot
        while (j >= low + 1 && arr[j] > pivot) j--;     // first element from the right that is <= pivot
        if (i < j) swap(arr, i, j);
    }
    swap(arr, low, j);                                  // pivot lands at its final index j
    return j;
}

Dry run of partition on arr = [4, 6, 2, 5, 7, 9, 1, 3], low = 0, high = 7, pivot = 4:

partition returns 3. The pivot 4 is at index 3, its position in the sorted array; [1, 3, 2] and [7, 9, 5, 6] are sorted recursively.

Complexity. Time O(n log n) on average and for random inputs: each partition is linear and a reasonably balanced pivot halves the problem, giving T(n) = 2T(n/2) + O(n). Worst case O(n^2) when the pivot is always the smallest or largest element, which with the first-element pivot happens on already sorted or reversed input: the recursion peels off one element per level, T(n) = T(n - 1) + O(n). Space O(log n) stack on average, O(n) in the worst case. No extra array is needed, which is quick sort’s advantage over merge sort.

Approach 2: Lomuto partition, pivot at the end

Intuition. The two-pointer partition is fast but its invariant is subtle. Lomuto’s partition trades a few extra swaps for an invariant you can state in one line: arr[low..i-1] holds the elements <= pivot seen so far. Scan j from low to high - 1; whenever arr[j] <= pivot, swap it into position i and grow the region. At the end swap the pivot (kept safe at arr[high]) into position i. Everything before i is <= pivot by construction, everything after is > pivot because it was skipped.

Algorithm.

1. pivot = arr[high], i = low.
2. For j from low to high - 1: if arr[j] <= pivot, swap arr[i] and arr[j], then i++.
3. Swap arr[i] and arr[high]; return i.

static void quickSortLomuto(int[] arr) {
    quickSortLomuto(arr, 0, arr.length - 1);
}

static void quickSortLomuto(int[] arr, int low, int high) {
    if (low >= high) return;
    int p = partitionLomuto(arr, low, high);
    quickSortLomuto(arr, low, p - 1);
    quickSortLomuto(arr, p + 1, high);
}

static int partitionLomuto(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low;                                        // arr[low..i-1] <= pivot
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    swap(arr, i, high);
    return i;
}

On Example 1 with pivot = 3: j = 2 finds 2, swapped to index 0; j = 6 finds 1, swapped to index 1; finally the pivot is swapped to index 2, giving [2, 1, 3, 5, 7, 9, 6, 4].

Complexity. Time O(n log n) average, O(n^2) worst (sorted input makes the last element the maximum, so p = high every time). Space O(log n) average stack. Lomuto does up to three times as many swaps as the two-pointer scheme on average and degrades to quadratic on all-equal input, because every element satisfies arr[j] <= pivot and the split is n - 1 to 0.

Approach 3: Three-way partition around the middle element

Intuition. Two weaknesses remain. First, picking the first or last element as pivot makes sorted input the worst case; picking the middle element makes sorted input the best case instead (random or median-of-three pivots achieve the same on average). Second, duplicates of the pivot are shuffled to one side and sorted again at the next level, which is wasted work; on an all-equal array both partitions above are quadratic.

Three-way partitioning (the Dutch national flag scheme) fixes the duplicate problem by splitting into three regions: < pivot, == pivot, > pivot. Pointers lt and gt mark the region boundaries and i scans. An element smaller than the pivot is swapped down to lt; a larger one is swapped up to gt (and i does not advance, because the swapped-in element is unexamined); an equal one just advances i. When i passes gt, every pivot-equal element is in its final place and only the outer regions recurse.

Algorithm.

1. If low >= high return. pivot = arr[mid], lt = low, i = low, gt = high.
2. While i <= gt: if arr[i] < pivot swap arr[lt], arr[i] and advance both; else if arr[i] > pivot swap arr[i], arr[gt] and decrement gt; else advance i.
3. Recurse on [low, lt - 1] and [gt + 1, high].

static void quickSortThreeWay(int[] arr) {
    quickSortThreeWay(arr, 0, arr.length - 1);
}

static void quickSortThreeWay(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = arr[low + (high - low) / 2];
    int lt = low, i = low, gt = high;                   // arr[low..lt-1] < pivot, arr[lt..i-1] == pivot, arr[gt+1..high] > pivot
    while (i <= gt) {
        if (arr[i] < pivot) swap(arr, lt++, i++);
        else if (arr[i] > pivot) swap(arr, i, gt--);
        else i++;
    }
    quickSortThreeWay(arr, low, lt - 1);
    quickSortThreeWay(arr, gt + 1, high);
}

static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Complexity. Time O(n log n) average; O(n) when all elements are equal (one partition, nothing left to recurse on); more generally O(n log k) for k distinct values. The worst case is still O(n^2) for adversarial inputs, but sorted and reversed arrays are no longer among them. Space O(log n) average stack.

Edge cases and pitfalls

• Empty or single-element array. quickSort(arr, 0, -1) or (0, 0) hits low >= high at once.
• <= on the left scan is not optional. In approach 1, if i advanced only while arr[i] < pivot, then on an all-equal array i would never move, j would never move, and the loop would swap the same two positions forever. The <= guarantees that i passes at least the pivot itself and makes progress after every swap.
• Bounds on the inner scans. i <= high - 1 keeps i from running past high when every element is <= pivot, and j >= low + 1 keeps j from running past low. Without them you index outside [low, high].
• Sorted input is the worst case for approaches 1 and 2. On n = 10^5 sorted elements that is 5 × 10^9 comparisons and 10^5 nested calls, which overflows the default JVM stack. Fixes: pick the middle element or a random pivot (Random with a fixed seed if you need reproducible runs), use median-of-three, or recurse on the smaller side and loop on the larger so the stack stays O(log n).
• Duplicates. Two-way partitions still sort correctly with duplicates (Example 2 passes), they are just slower. Use the three-way scheme when many equal keys are expected.
• Quick sort is not stable. Partition swaps move elements long distances past equal keys. When stability matters, use merge sort.
• Compare values, not differences. arr[i] - pivot <= 0 overflows near the int limits; the tests include Integer.MIN_VALUE and Integer.MAX_VALUE in one array.
• Return the pivot’s index, not i. In approach 1 the final swap uses j; returning i would place a non-pivot element at the boundary and the recursion would miss elements.

Related problems

• Sort an array of 0’s 1’s and 2’s is the three-way partition of approach 3 applied once, with 1 as the pivot.
• Merge Sorting is the other O(n log n) divide-and-conquer sort, stable but needing O(n) extra space.
• Insertion Sorting is what production quick sorts switch to for small sub-arrays.
• Selection Sort and Bubble Sort are the quadratic baselines that quick sort’s O(n log n) average beats.