Quick Sort

Quick sort is also divide-and-conquer, but it divides differently from merge sort: instead of always splitting at the midpoint and doing the hard work in the merge step, it picks a pivot element and partitions the array around it — everything smaller goes left, everything bigger goes right — so the hard work happens in the split, and the "combine" step is nothing at all (the pieces are already in their final relative order once every partition is sorted).

Divide and Conquer via Pivot Partitioning

Pick any element as the pivot, then rearrange the array so every element smaller than the pivot ends up before it and every element larger ends up after it. The pivot is now in its final sorted position. Recursively apply the same process to the sub-array left of the pivot and the sub-array right of it.

public static void quickSort(int[] arr, int low, int high) {
    if (low >= high) {
        return;                              // base case: 0 or 1 element
    }
    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);       // recurse left of pivot
    quickSort(arr, pivotIndex + 1, high);      // recurse right of pivot
}

Time complexity: O(n log n) average case — see the full derivation and worst-case analysis further down this page. Space complexity: O(log n) average — recursion stack depth matches the height of a balanced partition tree.

The Lomuto Partition Scheme, Fully Worked

The Lomuto scheme picks the last element as the pivot. It walks index j across the range; whenever it finds an element smaller than the pivot, it swaps that element into the next slot after a boundary pointer i, which tracks the end of the "confirmed smaller than pivot" region. At the end, the pivot is swapped into place right after that region.

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];        // Lomuto scheme: pivot is always the last element
    int i = low - 1;          // boundary: index of last element known to be < pivot

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;             // bring the smaller element into the "smaller than pivot" region
        }
    }
    // place the pivot right after the smaller-than-pivot region
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;                  // pivot's final, sorted index
}

Trace on [10, 80, 30, 90, 40] with pivot = 40 (last element): j=0, arr[0]=10<40 → i=0, swap arr[0] with arr[0] (no-op). j=1, arr[1]=80, not <40, skip. j=2, arr[2]=30<40 → i=1, swap arr[1] and arr[2] → [10, 30, 80, 90, 40]. j=3, arr[3]=90, not <40, skip. Loop ends with i=1, so swap arr[2] (80) with arr[4] (pivot 40) → [10, 30, 40, 90, 80]. Pivot 40 is now at index 2, its correct sorted position, with everything smaller to its left and everything larger to its right.

Time complexity: O(n) — the single pass over indices low..high does one comparison per element. Space complexity: O(1) — partitioning happens in place with only a couple of index variables.

Average O(n log n) vs Worst Case O(n²)

Just like a BST's height, quick sort's recursion depth depends entirely on how balanced each partition is. If the pivot consistently splits the array into two roughly equal halves, you get log n levels of partitioning, each doing O(n) work — O(n log n) overall, same shape as merge sort's derivation. But if the pivot is consistently the smallest or largest element, one side of the partition is empty and the other has everything else.

// Already-sorted input, using Lomuto's "always pick the last element" rule:
int[] arr = {1, 2, 3, 4, 5};
quickSort(arr, 0, arr.length - 1);

Space complexity: O(log n) average (recursion stack depth matches the balanced recursion tree height) but O(n) worst case (recursion depth matches the number of levels, which becomes n in the degenerate case above).

The Fix: Better Pivot Selection

The worst case above isn't really about quick sort being fragile — it's about the specific rule "always use the last element," which is trivially defeated by already-sorted (or reverse-sorted) input, a very common case in practice. Two standard fixes remove that predictability:

• Random pivot: swap a randomly chosen element into the last position before partitioning. An adversary can no longer construct a guaranteed-bad input, since the pivot choice isn't fixed.
• Median-of-three: look at the first, middle, and last elements, and use whichever is the median of the three as the pivot. This specifically defeats already-sorted and reverse-sorted inputs, the most common real-world worst cases.

private static int partitionRandomized(int[] arr, int low, int high) {
    int randomIndex = low + (int) (Math.random() * (high - low + 1));
    int temp = arr[randomIndex];
    arr[randomIndex] = arr[high];
    arr[high] = temp;                  // move random element into the pivot slot, then partition as usual
    return partition(arr, low, high);
}

Time complexity: expected O(n log n) — randomization makes the worst-case input pattern from above vanishingly unlikely rather than eliminating O(n²) entirely (an adversary who sees the random choices could still theoretically construct a bad case). Space complexity: O(log n) expected, same reasoning as above.

Why Quick Sort Often Beats Merge Sort in Practice