Quick Sort — The Versatile Performer

Introduction

In the previous post, we learned Merge Sort — a guaranteed $O(n \log n)$ algorithm that needs $O(n)$ extra space. Quick Sort takes a different approach: it achieves $O(n \log n)$ on average while sorting in-place (only $O(\log n)$ extra space for the recursion stack).

Quick Sort is the default sorting algorithm in many standard libraries (Java’s Arrays.sort() for primitives uses a variant of Quick Sort). Let’s understand why.

Think of this analogy: you’re organising books on a shelf. You pick one book at random — call it the pivot. You place all books that come before the pivot alphabetically to its left, and all books that come after it to its right. Now the pivot book is in its final correct position. You then repeat the same process for the left group and the right group separately.

How Quick Sort Works

1. Choose a pivot element from the array.
2. Partition the array: rearrange elements so that everything less than the pivot goes to the left, and everything greater goes to the right.
3. After partitioning, the pivot is in its final sorted position.
4. Recursively apply the same process to the left sub-array and the right sub-array.

Step-by-Step Walkthrough

Let’s sort [33, 15, 10, 45, 27, 8, 42] using the last element as pivot (Lomuto partition scheme).

Round 1 — Pivot = 42

We need to rearrange so that everything ≤ 42 goes left and everything > 42 goes right.

Walk through the array with a pointer i that tracks where the “small side” ends:

Now swap the pivot (42) into position i (index 5):

After partition: [33, 15, 10, 27, 8, **42**, 45] — 42 is in its final position ✅

• Left sub-array: [33, 15, 10, 27, 8]
• Right sub-array: [45] (single element, already sorted ✅)

Round 2 — Sort [33, 15, 10, 27, 8], Pivot = 8

Swap pivot (8) into position 0:

After partition: [**8**, 33, 15, 10, 27, 42, 45] — 8 is in place ✅

• Left sub-array: [] (empty)
• Right sub-array: [33, 15, 10, 27]

Round 3 — Sort [33, 15, 10, 27], Pivot = 27

Swap pivot into position 2:

After partition: [15, 10, **27**, 33] — 27 is in place ✅

Remaining rounds sort [15, 10] and [33]:

• Pivot = 10 → [**10**, 15] ✅
• [33] is a single element ✅

Final sorted array: [8, 10, 15, 27, 33, 42, 45] ✅

Java Implementation

public class QuickSort {

    /**
     * Entry point for Quick Sort.
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot's final index
            int pivotIndex = partition(arr, low, high);

            // Recursively sort elements before and after the pivot
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    /**
     * Lomuto partition scheme: uses the last element as pivot.
     * Returns the final index of the pivot after partitioning.
     */
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // choose the last element as pivot
        int i = low;           // i tracks the boundary of the "small" side

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

        // Place the pivot in its correct position
        swap(arr, i, high);
        return i;
    }

    private 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[] data = {33, 15, 10, 45, 27, 8, 42};
        quickSort(data, 0, data.length - 1);
        // Output: [8, 10, 15, 27, 33, 42, 45]
        for (int num : data) System.out.print(num + " ");
    }
}

Key Lines Explained

Pivot Strategies

The pivot choice dramatically affects performance:

Java’s Arrays.sort() for primitives uses dual-pivot Quick Sort — a variant that picks two pivots and partitions into three sections, offering even better real-world performance.

Time & Space Complexity

| Space | $O(\log n)$ — for the recursion stack | |:—:|:—:|

Tip: To avoid the $O(n^2)$ worst case in practice, use randomised pivot selection or the median-of-three strategy.

Merge Sort vs Quick Sort

Quick Sort wins in practice because it operates on contiguous memory (great for CPU cache), makes fewer data copies, and has a smaller constant factor.

When to Use / When NOT to Use

Practice Problems

1. Sort an Array – LeetCode #912 — Implement Quick Sort with random pivot. Compare its runtime against your Merge Sort solution.
2. Kth Largest Element – LeetCode #215 — Use the partition step (Quick Select) to find the k-th element in $O(n)$ average time without fully sorting.
3. Sort Colors – LeetCode #75 — A three-way partition problem inspired by Quick Sort (Dutch National Flag).

What’s Next?

We have now seen comparison-based sorts that top out at $O(n \log n)$. But can we do even better? Yes — when the data has special properties (integers in a known range), we can sort in linear time $O(n)$. Next up: Counting Sort, Radix Sort & Bucket Sort.