Quick Sort in C: Partition Trace and Bounded Stack

Quick sort in C partitions an array around a pivot and sorts the resulting ranges. This teaching implementation uses the last element as a pivot. It recurses on the smaller side and loops over the larger one, limiting call-stack depth without hiding the O(n²) worst-case running time.

Complete program

#include <stdio.h>
#include <stddef.h>

static void swap(int *a, int *b) {
    int temporary = *a; *a = *b; *b = temporary;
}

static size_t partition(int values[], size_t low, size_t high) {
    int pivot = values[high - 1];
    size_t boundary = low;
    for (size_t j = low; j < high - 1; ++j) {
        if (values[j] < pivot) {
            swap(&values[boundary], &values[j]);
            ++boundary;
        }
    }
    swap(&values[boundary], &values[high - 1]);
    return boundary;
}

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

void quick_sort(int values[], size_t count) {
    sort_range(values, 0, count);
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    quick_sort(values, count);
    for (size_t i = 0; i < count; ++i) printf("%s%d", i ? " " : "", values[i]);
    putchar('\n');
    return 0;
}

12 22 25 34 64

Trace the first partition

The range is half-open, [low, high). The pivot is 22. Before each scan, values before boundary are smaller than the pivot, and scanned values from boundary onward are not smaller.

The pivot at index 1 is now final. Sort [0,1) and [2,5). In the latter range pivot 34 leaves 25 34 64. The finished array is 12 22 25 34 64. Empty and one-element ranges immediately stop; excluding the placed pivot ensures progress even with duplicates.

Complexity, duplicates and stack depth

Balanced partitions give O(n log n) time. Under a random permutation of distinct keys, the usual average analysis is also O(n log n). But sorted, reverse-sorted and all-equal inputs can cause O(n²) work with this last-pivot, two-way partition. Do not label every input logarithmic, or assume duplicates automatically split evenly.

Each recursive call receives at most half the current elements; the larger side is handled by a loop. Therefore simultaneous recursion depth is O(log n), rather than the O(n) stack growth of naive two-sided recursion. Partitioning itself uses O(1) extra storage. This does not eliminate the quadratic number of comparisons. Randomized pivots reduce the chance of bad splits; three-way partitioning helps repeated keys. Neither is silently implemented here.

This version is not stable. With labeled keys 2a 2b 1, the pivot swap can produce 1 2b 2a, reversing equal records. The labels illustrate identity; they are not integer literals. Choose merge sort when stable merging is required, or heap sort for in-place worst-case O(n log n) time.

Array contract and common mistakes

The function modifies count writable integers. A null pointer with count zero is accepted; positive counts require a valid array. It does not allocate memory or read stdin. Half-open bounds avoid subtracting one from an unsigned zero index. The pivot is read only when the range contains at least two elements. Check all-equal, sorted, reverse, negative and duplicate values, plus INT_MIN and INT_MAX.

Do not recurse over a range that includes the placed pivot unchanged: that can prevent termination. Do not use integer subtraction as a comparator when values may span the full integer range. Test a small array using insertion sort to contrast shifting with partitioning.

Practice and answer

Trace 3 1 3 2: pivot 2 leaves 1 2 3 3, with pivot index 1. Values equal to the pivot are not moved into the smaller-than region by this strict comparison. For an all-equal array every pivot lands at the beginning of its current range, so work stays quadratic while recursive stack usage remains bounded. See the sorting table for trade-offs.