C Quick Sort

Pick a pivot, partition the array (smaller left, larger right), recursively sort each side. O(n log n) average, O(n²) worst case. In-place; usually the fastest sort in practice.

Quicksort is the workhorse — qsort in the C stdlib is typically a quicksort variant. Faster than mergesort in practice due to better cache behavior and no extra memory.

The basic shape

#include <stdio.h>

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

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

void quick_sort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
  }
}

int main() {
  int nums[] = {10, 80, 30, 90, 40, 50, 70};
  int n = sizeof(nums) / sizeof(nums[0]);

  quick_sort(nums, 0, n - 1);

  for (int i = 0; i < n; i++) printf("%d ", nums[i]);
  printf("\n");
  // 10 30 40 50 70 80 90
}

Divide and conquer (different from mergesort)

Mergesort divides into equal halves first, then merges. Quicksort divides into "small" and "large" halves around a pivot, no merge needed.

void quick_sort(int arr[], int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
  }
}

Partition rearranges the array so: - All elements before pi are ≤ pivot. - All elements after pi are > pivot. - The pivot is at index pi (its final position).

Recursively sort the two sides. The pivot is already in place — no merge.

partition — Lomuto's scheme

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

This is the Lomuto partition scheme. Pick the last element as pivot. Walk through, swapping smaller elements toward the front.

After the loop, i is the last "smaller-than-pivot" position. The pivot lands at i + 1.

Before:  [10, 80, 30, 90, 40, 50, 70]   pivot = 70
After:   [10, 30, 40, 50, 70, 90, 80]   pivot lands at index 4

Everything before 70 is ≤ 70; everything after is > 70.

Hoare's partition (alternative)

Hoare's scheme (the original from the 1961 paper) uses two pointers moving toward each other:

int hoare_partition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low - 1;
  int j = high + 1;
  while (1) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    swap(&arr[i], &arr[j]);
  }
}

Slightly more efficient (fewer swaps on average) but trickier to implement correctly. Most textbooks use Lomuto for clarity.

Complexity

The worst case is O(n²) — happens when the pivot is always the smallest or largest. For an already-sorted array with last-element pivot: every partition is degenerate.

Avoiding the worst case

Random pivot. Pick a random index, swap to last, then partition. Hard to construct adversarial input.

Median-of-three. Pick the median of arr[low], arr[mid], arr[high] as pivot. Robust against sorted/reverse-sorted/equal-values inputs.

Introsort — start with quicksort, switch to heapsort if recursion depth exceeds log₂(n). Guarantees O(n log n) worst case. Used in std::sort and many qsort implementations.

Recursion depth

For balanced pivots, log₂(n) levels. For 1 million elements, ~20 stack frames — fine.

For pathological pivots (always smallest), n levels — 1 million stack frames → stack overflow. Tail-recursion elimination on the larger side reduces this:

void quick_sort(int arr[], int low, int high) {
  while (low < high) {
    int pi = partition(arr, low, high);
    if (pi - low < high - pi) {
      quick_sort(arr, low, pi - 1);
      low = pi + 1;
    } else {
      quick_sort(arr, pi + 1, high);
      high = pi - 1;
    }
  }
}

Recurse on the smaller side; loop on the larger. Stack depth always O(log n).

Stability

Quicksort is not stable. Equal elements may swap order during partitioning.

If stability matters, use mergesort or qsort (which is implementation-defined — POSIX doesn't require stability).

Real-world: stdlib qsort

#include <stdlib.h>

int compare(const void *a, const void *b) {
  return (*(int *)a) - (*(int *)b);
}

int nums[] = {64, 25, 12, 22, 11};
qsort(nums, 5, sizeof(int), compare);

qsort from <stdlib.h> is generic — works on any type via void * and a comparator.

The implementation may be quicksort, introsort, or merge sort — depends on the library. Performance is excellent.

For real code, use qsort. Implement quicksort yourself only for learning or for narrow performance reasons.

When to use which sort

Most production code: qsort or stdlib equivalent. Custom implementations for narrow needs.

Common mistakes

Returning pi - 1 from partition. Off-by-one. Lomuto returns the pivot's final position; you recurse on pi - 1 and pi + 1.

Using <= in partition's inner condition. Affects which equal-valued elements end up on which side. Slight performance/stability tradeoff.

Recurse before partition. Order of operations: partition first, then recurse on the resulting subarrays.

Pivot at random index, partition expects pivot at end. If you swap a random pivot to arr[high], then Lomuto works. Don't forget the swap.

Stack overflow on adversarial input. Always use median-of-three or random pivot for production.

What's next

Episode 56: dynamic arrays. A grow-on-demand array with amortized O(1) push.

Recap

Quicksort: pick pivot, partition (smaller left, larger right), recurse on each side. O(n log n) average, O(n²) worst. In-place — only O(log n) stack space. Lomuto's partition scheme is simpler; Hoare's is faster. Pivot choice matters — median-of-three or random for production. Not stable. For real code, use qsort from stdlib. For huge arrays, introsort (quicksort + heapsort fallback) gives both speed and worst-case guarantees.

Next episode: dynamic arrays.