Quick Sort

A divide-and-conquer sorting algorithm with excellent average performance and a dangerous worst case.

Context

Quick sort is fast because it works in-place and minimises memory access.
It’s also fragile, cause a bad pivot choice leads to quadratic time.

Core idea

• pick a pivot element
• partition the array so:
  • elements ≤ pivot go left
  • elements > pivot go right
• recursively sort both partitions

The key operation is partitioning, not recursion.

Properties

• Time complexity
  • Average: O(n log n)
  • Worst case: O(n²) (bad pivots)
• Space complexity: O(log n) (recursion stack)
• Not stable: partitioning swaps distant elements.
• In-place: no auxiliary arrays.

Pivot Selection

• First / Last:
  • always array[lo] or array[hi]
  • already sorted, or reverse-sorted array: worst case every time
• Random Pivot:
  • pick a random index in [lo, hi]
  • swap it to the end and partition normally
  • worst case still exists but becomes unlikely
  • additional cost of generating a random number per iteration
• Middle Element:
  • often better than first / last
• Median-Of-Three
  • take array[lo], array[mid] and array[hi]
  • use their median as the pivot
  • additional costs of a few comparisons per iterations

Implementation

class QuickSort {
    private static final Random random = new Random();

    static void quickSort(int[] array, int lo, int hi, PivotStrategy strategy) {
        if (lo >= hi) return;

        var pivotIndex = partition(array, lo, hi, strategy);
        quickSort(array, lo, pivotIndex - 1, strategy);
        quickSort(array, pivotIndex + 1, hi, strategy);
    }

    private static int partition(int[] array, int lo, int hi, PivotStrategy strategy) {
        int pivot = getPivot(array, lo, hi, strategy);

        int idx = lo - 1;

        for (var i = lo; i < hi; i++) {
            if (array[i] <= pivot) {
                swap(array, i, ++idx);
            }
        }
        
        swap(array, hi, ++idx);
        return idx;
    }

    private static int getPivot(int[] array, int lo, int hi, PivotStrategy strategy) {
        return switch (strategy) {
            case LAST -> array[hi];
            
            case RANDOM -> {
                var idx = random.nextInt(lo, hi + 1);
                swap(array, hi, idx);
                yield array[hi];
            }
            
            case MEDIAN_OF_THREE -> {
                int midIndex = lo + (hi - lo) / 2;
                int low = array[lo];
                int mid = array[midIndex];
                int high = array[hi];

                int medianIndex;

                if ((low <= mid && mid <= high) || (high <= mid && mid <= low)) {
                    medianIndex = midIndex;
                } else if ((mid <= low && low <= high) || (high <= low && low <= mid)) {
                    medianIndex = lo;
                } else {
                    medianIndex = hi;
                }
                swap(array, hi, medianIndex);
                yield array[hi];
            }
        };
    }

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

    enum PivotStrategy {
        LAST,
        RANDOM,
        MEDIAN_OF_THREE
    }
}