QuickSort

QuickSort partitions a range around a pivot and recursively sorts the partitions. It is often fast in memory but requires care with pivots, duplicates, and stack depth.

static void quickSort(int[] values) {
    quickSort(values, 0, values.length - 1);
}

private static void quickSort(int[] values, int low, int high) {
    while (low < high) {
        int pivot = partition(values, low, high);
        if (pivot - low < high - pivot) {
            quickSort(values, low, pivot - 1);
            low = pivot + 1;
        } else {
            quickSort(values, pivot + 1, high);
            high = pivot - 1;
        }
    }
}

private static int partition(int[] values, int low, int high) {
    int pivotValue = values[high];
    int boundary = low;
    for (int scan = low; scan < high; scan++) {
        if (values[scan] <= pivotValue) swap(values, boundary++, scan);
    }
    swap(values, boundary, high);
    return boundary;
}

private static void swap(int[] values, int first, int second) {
    int temporary = values[first];
    values[first] = values[second];
    values[second] = temporary;
}

The example chooses the last value for clarity. During partitioning, values before boundary are at most the pivot and scanned values after it are greater. Placing the pivot at boundary establishes its final position; induction proves the recursive result.

Balanced partitions cost Θ(n log n). Randomized pivoting has expected Θ(n log n) time, not an absolute guarantee; consistently extreme pivots cost Θ(n²). Partitioning uses Θ(1) storage, and recursing only on the smaller side bounds stack depth by O(log n). The algorithm is not stable. Three-way partitioning is preferable when many keys equal the pivot.