Idea: Partition around a pivot

• Average: O(n log n)
• Worst: O(n²)
• Space: O(log n)
• Stable: ❌

Why popular

• Fast in practice
• Cache-friendly

Java note

• Used for primitives (Arrays.sort(int[]))

public class QuickSort {
    public static void sort(int[] a) {
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int l, int r) {
        if (l >= r) return;
        int p = partition(a, l, r);
        quick(a, l, p - 1);
        quick(a, p + 1, r);
    }

    // Lomuto partition with pivot=a[r]
    private static int partition(int[] a, int l, int r) {
        int pivot = a[r];
        int i = l; // place for next smaller/equal
        for (int j = l; j < r; j++) {
            if (a[j] <= pivot) swap(a, i++, j);
        }
        swap(a, i, r);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Watch for

• Pivot selection
• Partitioning around pivot
• Recursive sorting

Mental model: ⚡ Pivot decides everything