Chapter 19 of 65

Quick Sort

Imagine you're arranging students in a line by height. Instead of comparing everyone with everyone, you pick one student, say Rahul, and tell the class:

"Everyone shorter than Rahul, stand on his left.
 Everyone taller than Rahul, stand on his right."

After this one instruction, Rahul is standing in exactly the right spot. He never needs to move again. Now you repeat the same trick separately on the left group and the right group.

That's Quick Sort.

Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element, partitions the array so that smaller elements go to the left of the pivot and larger elements go to the right, and then recursively sorts the two parts.

Quick Sort is one of the most widely used sorting algorithms. It sorts in place, it is very fast in practice, and its partition idea shows up in many interview problems.


The Core Idea

Like Merge Sort, Quick Sort uses divide and conquer, but it splits the work differently:

Step

Merge Sort

Quick Sort

Divide

Split at the middle index (trivial)

Partition around a pivot (real work)

Conquer

Sort both halves recursively

Sort both parts recursively

Combine

Merge the halves (real work)

Nothing to do

In Merge Sort, the hard work happens after the recursive calls. In Quick Sort, it happens before them, in the partition step.

The algorithm is:

quickSort(arr, low, high):

    if low < high:
        p = partition(arr, low, high)   // pivot lands at index p
        quickSort(arr, low, p - 1)      // sort the left part
        quickSort(arr, p + 1, high)     // sort the right part

After partitioning, the array looks like this:

[ elements < pivot | pivot | elements ≥ pivot ]
                       ↑
            already in its final position

Notice that the left and right parts are not sorted yet. We only know that every element on the left is smaller than the pivot. Sorting each part is the job of the recursive calls.


Lomuto Partition

There are several ways to partition. The easiest one to understand is the Lomuto partition scheme:

  • Choose the last element as the pivot.

  • Keep a pointer i that marks the end of the "smaller than pivot" region.

  • Scan the array with j. Whenever arr[j] < pivot, grow the smaller region by one and swap arr[j] into it.

  • Finally, swap the pivot into position i + 1.

While scanning, the array always has this shape:

[ < pivot | ≥ pivot | not checked yet | pivot ]
 low     i         j                  high

Partition Step by Step

Let's partition:

[10, 80, 30, 90, 40, 50, 70]
pivot = 70 (last element), i = -1
j = 0: 10 < 70 → i = 0, swap arr[0] and arr[0]
       [10, 80, 30, 90, 40, 50, 70]

j = 1: 80 ≥ 70 → do nothing
       [10, 80, 30, 90, 40, 50, 70]

j = 2: 30 < 70 → i = 1, swap arr[1] and arr[2]
       [10, 30, 80, 90, 40, 50, 70]

j = 3: 90 ≥ 70 → do nothing
       [10, 30, 80, 90, 40, 50, 70]

j = 4: 40 < 70 → i = 2, swap arr[2] and arr[4]
       [10, 30, 40, 90, 80, 50, 70]

j = 5: 50 < 70 → i = 3, swap arr[3] and arr[5]
       [10, 30, 40, 50, 80, 90, 70]

The scan is done. Now place the pivot right after the smaller region, at index i + 1 = 4:

swap arr[4] and arr[6]

[10, 30, 40, 50, 70, 90, 80]
 \____________/  ↑  \_____/
    < 70        70    > 70

70 is now in its final sorted position. Quick Sort then recursively sorts [10, 30, 40, 50] and [90, 80].


Quick Sort in Java

Here's the complete program using Lomuto partition. It prints the array after every partition.

import java.util.Arrays;

class Main {

    static void quickSort(int[] arr, int low, int high) {

        if (low < high) {

            int p = partition(arr, low, high);

            quickSort(arr, low, p - 1);    // left of pivot
            quickSort(arr, p + 1, high);   // right of pivot
        }
    }

    // Lomuto partition: last element is the pivot
    static int partition(int[] arr, int low, int high) {

        int pivot = arr[high];
        int i = low - 1;   // end of the "smaller than pivot" region

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);   // put pivot in its final place

        System.out.println("Pivot " + pivot + " -> index " + (i + 1)
            + ": " + Arrays.toString(arr));

        return i + 1;
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {10, 80, 30, 90, 40, 50, 70};

        quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Output:

Pivot 70 -> index 4: [10, 30, 40, 50, 70, 90, 80]
Pivot 50 -> index 3: [10, 30, 40, 50, 70, 90, 80]
Pivot 40 -> index 2: [10, 30, 40, 50, 70, 90, 80]
Pivot 30 -> index 1: [10, 30, 40, 50, 70, 90, 80]
Pivot 80 -> index 5: [10, 30, 40, 50, 70, 80, 90]
Sorted: [10, 30, 40, 50, 70, 80, 90]

Look at the left part [10, 30, 40, 50]. It was already sorted, so the last element was always the largest. Each partition only removed one element (50, then 40, then 30). Keep this in mind, because it is exactly what causes Quick Sort's worst case.


Time Complexity

Partitioning a range of n elements scans it once, so it takes O(n). The total time depends on how evenly the pivot splits the array.

Best Case: Pivot Splits in the Middle

              n
           /     \
        n/2       n/2
       /   \     /   \
     n/4  n/4  n/4   n/4
       ...

This is the same shape as Merge Sort: log n levels with O(n) work per level.

T(n) = 2 T(n/2) + O(n)  →  O(n log n)

Worst Case: Pivot Is Always the Smallest or Largest

If the array is already sorted and we always pick the last element, the pivot is always the maximum. One side gets n - 1 elements and the other side gets nothing:

n
 \
  n-1
    \
    n-2
      \
      ...
        \
         1
Work = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2  →  O(n²)

Average Case

On random data, the pivot usually lands somewhere reasonable. Even a consistently lopsided split like 10% / 90% still gives O(log n) levels, so the average is:

O(n log n)

Seeing the Difference

Let's count the comparisons Quick Sort (last-element pivot) makes on 1,000 numbers, first shuffled and then already sorted:

import java.util.Random;

class Main {

    static long comparisons;

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            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[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            comparisons++;
            if (arr[j] < pivot) {
                i++;
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
            }
        }
        int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
        return i + 1;
    }

    public static void main(String[] args) {

        int n = 1000;

        int[] sorted = new int[n];
        for (int i = 0; i < n; i++) sorted[i] = i;

        int[] shuffled = sorted.clone();
        Random rnd = new Random(42);
        for (int i = n - 1; i > 0; i--) {          // Fisher-Yates shuffle
            int j = rnd.nextInt(i + 1);
            int t = shuffled[i]; shuffled[i] = shuffled[j]; shuffled[j] = t;
        }

        comparisons = 0;
        quickSort(shuffled, 0, n - 1);
        System.out.println("Shuffled input: " + comparisons + " comparisons");

        comparisons = 0;
        quickSort(sorted, 0, n - 1);
        System.out.println("Sorted input:   " + comparisons + " comparisons");
    }
}

Output:

Shuffled input: 11482 comparisons
Sorted input:   499500 comparisons

The sorted input needs exactly 1000 × 999 / 2 = 499,500 comparisons, more than 40 times the shuffled case. (Using a fixed seed 42 makes the shuffle, and therefore the output, the same on every run.)

Case

Time

When it happens

Best

O(n log n)

Pivot always near the median

Average

O(n log n)

Random data or random pivot

Worst

O(n²)

Pivot always the min or max (e.g. sorted input with first/last pivot)


Space Complexity

Quick Sort partitions in place, so it doesn't need a temporary array like Merge Sort. The only extra memory is the recursion call stack:

Balanced splits  → recursion depth O(log n) → O(log n) space
Worst case       → recursion depth O(n)     → O(n) space

That worst-case depth is a real problem in Java. Running the simple version above on an already sorted array of just a few tens of thousands of elements can throw a StackOverflowError with default JVM settings. We'll fix this below.


Quick Sort Is Not Stable

Partitioning swaps elements across long distances, so equal elements can change their relative order.

For example, partitioning [5a, 5b, 1] with pivot 1 swaps 1 with 5a:

Before: [5a, 5b, 1]
After:  [1, 5b, 5a]

5a and 5b are equal but their order has flipped. That's why Java uses a merge-based sort (TimSort), not Quick Sort, when sorting objects, where stability matters.


Choosing a Better Pivot

The worst case happens when the pivot is consistently a bad choice. Common fixes:

1. Random Pivot

Pick a random index, swap it to the end, and partition as usual.

import java.util.Arrays;
import java.util.Random;

class Main {

    static final Random random = new Random();

    static void quickSort(int[] arr, int low, int high) {

        if (low < high) {
            int p = randomizedPartition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    static int randomizedPartition(int[] arr, int low, int high) {

        // Pick a random index in [low, high] and move it to the end
        int r = low + random.nextInt(high - low + 1);
        swap(arr, r, high);

        return partition(arr, low, high);   // normal Lomuto
    }

    static int partition(int[] arr, int low, int high) {

        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

Output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

The input here is already sorted, the classic worst case for a fixed last-element pivot. With a random pivot, no particular input is consistently bad. The worst case is still O(n²) in theory, but its probability is tiny, and the expected running time is O(n log n) for every input.

2. Median of Three

Look at the first, middle and last elements and use the median of the three as the pivot. For sorted or reverse-sorted input, this picks the true middle element instead of the minimum or maximum, so the splits stay balanced.

[1, 2, 3, 4, 5, 6, 7, 8, 9]
 ↑           ↑           ↑
 1           5           9   → median = 5

Hoare Partition

The original partition scheme, invented by Tony Hoare (who created Quick Sort in 1959), uses two pointers moving toward each other:

  • i moves right until it finds an element ≥ pivot.

  • j moves left until it finds an element ≤ pivot.

  • If they haven't crossed, swap them and continue.

import java.util.Arrays;

class Main {

    static void quickSort(int[] arr, int low, int high) {

        if (low < high) {

            int p = hoarePartition(arr, low, high);

            quickSort(arr, low, p);        // note: p, not p - 1
            quickSort(arr, p + 1, high);
        }
    }

    // Hoare partition: first element is the pivot
    static int hoarePartition(int[] arr, int low, int high) {

        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;

        while (true) {

            do {
                i++;
            } while (arr[i] < pivot);

            do {
                j--;
            } while (arr[j] > pivot);

            if (i >= j) {
                return j;
            }

            swap(arr, i, j);
        }
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {10, 80, 30, 90, 40, 50, 70};

        quickSort(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

Output:

[10, 30, 40, 50, 70, 80, 90]

Two important differences from Lomuto:

  • Hoare returns a split point j, not the pivot's final position. Everything in low..j is ≤ pivot and everything in j+1..high is ≥ pivot. That's why the recursive call is quickSort(arr, low, p), not p - 1.

  • Hoare does about three times fewer swaps on average and handles many duplicates much better, which is why it is usually faster in practice.

Property

Lomuto

Hoare

Pivot in this code

Last element

First element

Returns

Pivot's final index

A split point

Recursive calls

(low, p-1) and (p+1, high)

(low, p) and (p+1, high)

Swaps

More

Fewer

All-equal array

O(n²)

O(n log n) (balanced splits)

Ease of understanding

Easier

Trickier


Handling Many Duplicates: 3-Way Partition

What if the array is something like [4, 4, 4, 4, 4, ...]? With Lomuto, every element equal to the pivot ends up on one side, so the splits become completely lopsided and the time becomes O(n²).

The fix is 3-way partitioning (also called the Dutch National Flag partition). It splits the range into three groups:

[ < pivot | == pivot | > pivot ]
           lt       gt

The middle group is already in its final place, so we recurse only on the left and right groups.

import java.util.Arrays;

class Main {

    static void quickSort3Way(int[] arr, int low, int high) {

        if (low >= high) {
            return;
        }

        int pivot = arr[low];
        int lt = low;      // arr[low..lt-1]   < pivot
        int i = low;       // arr[lt..i-1]     == pivot
        int gt = high;     // arr[gt+1..high]  > pivot

        while (i <= gt) {
            if (arr[i] < pivot) {
                swap(arr, lt, i);
                lt++;
                i++;
            } else if (arr[i] > pivot) {
                swap(arr, i, gt);
                gt--;      // i stays: the value swapped in is not checked yet
            } else {
                i++;
            }
        }

        quickSort3Way(arr, low, lt - 1);
        quickSort3Way(arr, gt + 1, high);
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};

        quickSort3Way(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));
    }
}

Output:

[1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]

In the first partition, all eight 4s are placed at once and never touched again. This same three-pointer idea solves the famous Sort Colors problem (sort an array of 0s, 1s and 2s in one pass).


Limiting the Stack: Recurse on the Smaller Side

We can guarantee O(log n) stack space, even in the worst case, with a simple trick: make a recursive call only for the smaller part, and handle the larger part with a loop.

static void quickSort(int[] arr, int low, int high) {

    while (low < high) {

        int p = partition(arr, low, high);

        if (p - low < high - p) {
            quickSort(arr, low, p - 1);   // smaller part: recurse
            low = p + 1;                  // larger part: loop
        } else {
            quickSort(arr, p + 1, high);  // smaller part: recurse
            high = p - 1;                 // larger part: loop
        }
    }
}

Each recursive call handles at most half of the current range, so the depth can never exceed log₂ n. The time is still O(n²) in the worst case, but the program will no longer crash with a StackOverflowError.


Bonus: Quickselect

Partition puts the pivot at its final sorted index. We can use this to find the k-th smallest element without fully sorting.

After partitioning:

p == k - 1  → the pivot is the answer
p > k - 1   → the answer is in the left part
p < k - 1   → the answer is in the right part

Unlike Quick Sort, we only recurse into one side.

class Main {

    // Returns the k-th smallest element (k is 1-based)
    static int quickSelect(int[] arr, int low, int high, int k) {

        int p = partition(arr, low, high);

        if (p == k - 1) {
            return arr[p];
        } else if (p > k - 1) {
            return quickSelect(arr, low, p - 1, k);    // go left only
        } else {
            return quickSelect(arr, p + 1, high, k);   // go right only
        }
    }

    static int partition(int[] arr, int low, int high) {

        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {

        int[] arr = {7, 10, 4, 3, 20, 15};
        int n = arr.length;

        System.out.println("3rd smallest: "
            + quickSelect(arr.clone(), 0, n - 1, 3));

        // k-th largest = (n - k + 1)-th smallest
        System.out.println("2nd largest: "
            + quickSelect(arr.clone(), 0, n - 1, n - 2 + 1));
    }
}

Output:

3rd smallest: 7
2nd largest: 15

The sorted array would be [3, 4, 7, 10, 15, 20], so both answers are correct.

Because we only follow one side, the average work is n + n/2 + n/4 + ... ≈ 2n:

Quickselect average → O(n)
Quickselect worst   → O(n²)  (use a random pivot to avoid it in practice)

That beats sorting first, which costs O(n log n).


Common Mistakes

1. Mixing up Lomuto and Hoare recursion ranges

With Lomuto, use (low, p - 1) and (p + 1, high). With Hoare, use (low, p) and (p + 1, high). Using Lomuto's ranges with Hoare's partition can skip elements or leave the array unsorted, and using (low, p) with Lomuto can recurse forever.

2. Wrong base case

The condition must be if (low < high). Without it, the recursion has no stopping point: partition() gets called on empty ranges like (0, -1), reads an invalid index such as arr[-1], and the program crashes.

3. Forgetting the final pivot swap in Lomuto

Without swap(arr, i + 1, high), the pivot stays at the end and the returned index is wrong.

4. Using a fixed first/last pivot on sorted data

This is the classic way to hit O(n²) time and a stack overflow. Use a random pivot or median of three.

5. Assuming Quick Sort is stable

It is not. If you need stability, use Merge Sort.


Quick Sort vs Merge Sort

Property

Quick Sort

Merge Sort

Average time

O(n log n)

O(n log n)

Worst time

O(n²)

O(n log n)

Extra space

O(log n) stack (average)

O(n)

In-place

Yes

No (for arrays)

Stable

No

Yes

Where the work happens

Before recursion (partition)

After recursion (merge)

Practical speed on arrays

Usually faster (cache friendly, no copying)

Slightly slower

Best for

Primitive arrays in memory

Linked lists, stable sorts, external sorting

What Java Actually Uses

  • Arrays.sort(int[]) and other primitive arrays use Dual-Pivot Quicksort (by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch). It uses two pivots to split the array into three parts. The current Java documentation states that it offers O(n log n) performance on all data sets, because modern versions fall back to other techniques when the recursion gets too deep.

  • Arrays.sort(Object[]) and Collections.sort() use TimSort, a stable merge-based sort, because objects often need stability.

For primitives like int, stability doesn't matter, since two equal int values are indistinguishable.


Interview Tips and Practice

  • Be able to write Lomuto partition from memory and trace it on a small array.

  • Know exactly when the worst case happens and two ways to avoid it (random pivot, median of three).

  • Explain why Quick Sort is often faster than Merge Sort despite its worse worst case: in-place, fewer data copies, good cache behaviour.

  • For "k-th largest/smallest" questions, mention Quickselect (O(n) average) as an alternative to sorting.

Practice problems:

  • Sort an Array (LeetCode 912). A plain last-element pivot may time out on sorted inputs, so try a random pivot, and use 3-way partition for arrays with many duplicates.

  • Sort Colors (LeetCode 75): 3-way partition

  • Kth Largest Element in an Array (LeetCode 215): Quickselect

  • K Closest Points to Origin (LeetCode 973): Quickselect on distances

  • Move all negative numbers to one side of the array: a single partition pass


The Main Idea

Quick Sort picks a pivot, partitions the array around it, and recursively sorts the two sides.

Pick a pivot
     ↓
Partition: smaller left, larger right
     ↓
Pivot is now in its final position
     ↓
Recursively sort left and right parts

Its key facts:

Best / Average → O(n log n)
Worst          → O(n²)  (bad pivots, e.g. sorted input + last-element pivot)
Space          → O(log n) average stack, O(n) worst
In-place       → Yes
Stable         → No

Quick Sort is usually the fastest general-purpose in-memory sort, as long as the pivot is chosen wisely. Its partition step is also the foundation of Quickselect and the Dutch National Flag problem.

So far, every algorithm has sorted by comparing elements. In the next chapter, we'll see Counting Sort and Radix Sort, which sort integers without comparing them at all and can beat O(n log n).