Premium

Quick Sort

Basic Algorithms
≈ 2 min read

Partition the array around a pivot

Quick sort chooses a pivot and rearranges the values so that elements smaller than or equal to it end up on one side and larger elements on the other. After this partitioning, the two parts can be sorted independently in the same way. 

static int partition(int[] a, int left, int right) {
    int pivot = a[right];
    int boundary = left;

    for (int i = left; i < right; i++) {
        if (a[i] <= pivot) {
            int tmp = a[i];
            a[i] = a[boundary];
            a[boundary] = tmp;
            boundary++;
        }
    }

    int tmp = a[boundary];
    a[boundary] = a[right];
    a[right] = tmp;
    return boundary;
}

After partition, the pivot is already in its final position. Values not greater than the pivot are on the left, and larger values are on the right. Quick sort then recursively repeats the same operation for the left and right parts.

Average and worst case

If the partitions are reasonably balanced, the recursion depth is about log n and the total work is O(n log n). But if the pivot repeatedly becomes almost the smallest or largest value, the parts become extremely uneven and the running time can degrade to O(n²).

Why pivot choice matters

The partitioning idea stays the same, but the pivot-selection strategy strongly affects the chance of bad splits. Practical implementations use different selection techniques so that performance does not depend on one obvious input arrangement.

Quick sort usually rearranges the original array, but recursion still uses call-stack memory. With good partitions this is about O(log n), while extremely bad partitions can increase it to O(n).
Back Next