C Quicksort
Quicksort is a fast, in-place, divide-and-conquer sorting algorithm that is one of the most commonly used sorting routines in real software, including many implementations behind C’s own qsort(). Instead of comparing every pair of elements like bubble sort, it repeatedly splits the array around a chosen pivot value so that everything smaller ends up on one side and everything larger ends up on the other, then recursively sorts each side. Learning to implement quicksort correctly by hand also teaches you the partitioning technique that shows up in many other algorithms, such as finding the median or the k-th smallest element. This lesson builds a correct quicksort from scratch in C, explains exactly what the partition step does, and covers the mistakes that trip up almost everyone the first time.
Overview: How Quicksort Works
Quicksort is a divide-and-conquer algorithm with three steps applied recursively to a range of the array:
- Choose a pivot — pick one element from the array (commonly the first, last, middle, or a randomly chosen element).
- Partition — rearrange the array in place so that every element less than the pivot comes before it, and every element greater comes after it. After partitioning, the pivot sits at its final sorted position.
- Recurse — apply the same process to the sub-array to the left of the pivot and the sub-array to the right of the pivot.
The recursion bottoms out when a sub-array has zero or one elements, since a single element is trivially “sorted”. Because the partition step does all its work by swapping elements within the original array, quicksort is an in-place sort — it needs no second array, only O(log n) extra memory for the recursion’s call stack (each recursive call is a stack frame holding the low and high bounds it was given).
On average, each partition splits the array roughly in half, giving a recursion tree of depth O(log n), with O(n) work done at each level to scan and swap elements — hence the well-known average time complexity of O(n log n). However, if the pivot choice is unlucky (for example, always picking the first element on an already-sorted array), one side of the partition can end up empty every time, producing a recursion depth of O(n) and a worst case of O(n²). This is the single biggest practical gotcha with quicksort and is discussed in detail below.
Quicksort is also not stable: two elements that compare equal are not guaranteed to keep their original relative order, because the partition step swaps elements based purely on comparisons to the pivot, without regard for where equal elements originally sat.
Syntax
A typical C quicksort is written as two functions: a partition() function that rearranges one sub-array and returns the pivot’s final index, and a quicksort() function that recurses on both sides:
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // partition and get pivot index
quicksort(arr, low, pi - 1); // recursively sort left part
quicksort(arr, pi + 1, high); // recursively sort right part
}
}| Part | Meaning |
|---|---|
arr[] |
The array being sorted, passed by reference (arrays decay to pointers in C). |
low, high |
Inclusive index bounds of the sub-array currently being sorted. |
partition() |
Rearranges arr[low..high] around a pivot and returns the pivot’s final index pi. |
if (low < high) |
The base case: a sub-array of 0 or 1 elements needs no further work. |
The initial call from main() is always quicksort(arr, 0, n - 1), where n is the number of elements.
Examples
Example 1: Classic Quicksort with the Lomuto Partition Scheme
The most common beginner-friendly partition scheme is the Lomuto scheme, which always picks the last element of the range as the pivot.
#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 quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void) {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
quicksort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}Output:
Original array: 10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10 i tracks the boundary of elements known to be smaller than the pivot. As j scans the range, any element smaller than the pivot is swapped into the growing “smaller” region. Once the loop finishes, the pivot itself is swapped into place right after that region, which is exactly where it belongs in the final sorted order.
Example 2: Sorting an Array of Strings
Quicksort works on any type that can be compared and swapped — not just numbers. Here it sorts an array of C strings (char *) alphabetically using strcmp() instead of <.
#include <stdio.h>
#include <string.h>
void swap(char *arr[], int i, int j) {
char *temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(char *arr[], int low, int high) {
char *pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (strcmp(arr[j], pivot) < 0) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
void quicksort(char *arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
int main(void) {
char *names[] = {"Charlie", "Alice", "Eve", "Bob", "David"};
int n = sizeof(names) / sizeof(names[0]);
printf("Before: ");
for (int i = 0; i < n; i++) {
printf("%s ", names[i]);
}
printf("\n");
quicksort(names, 0, n - 1);
printf("After: ");
for (int i = 0; i < n; i++) {
printf("%s ", names[i]);
}
printf("\n");
return 0;
}Output:
Before: Charlie Alice Eve Bob David
After: Alice Bob Charlie David Eve Only two things changed from Example 1: the comparison arr[j] < pivot became strcmp(arr[j], pivot) < 0, and swap() now exchanges pointers instead of integers. This is the general pattern for adapting quicksort to any data type: change the comparison and the swap, keep the partitioning logic identical.
Example 3: The Hoare Partition Scheme
Tony Hoare’s original partition scheme (from 1961) uses two pointers that scan inward from both ends and is typically faster in practice than Lomuto because it does roughly three times fewer swaps on average. Its recursive calls use (low, pi) and (pi + 1, high) — note this differs from Lomuto’s pi - 1 / pi + 1 split, because Hoare’s returned index is not guaranteed to hold the pivot itself.
#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int hoarePartition(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]);
}
}
void quicksort(int arr[], int low, int high) {
if (low < high) {
int pi = hoarePartition(arr, low, high);
quicksort(arr, low, pi);
quicksort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main(void) {
int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original (reverse-sorted): ");
printArray(arr, n);
quicksort(arr, 0, n - 1);
printf("Sorted: ");
printArray(arr, n);
return 0;
}Output:
Original (reverse-sorted): 9 8 7 6 5 4 3 2 1
Sorted: 1 2 3 4 5 6 7 8 9 Here the pivot is the first element. The inner i pointer walks right until it finds an element that belongs on the pivot’s right, the j pointer walks left until it finds an element that belongs on the pivot’s left, and the two are swapped. This repeats until the pointers cross, at which point j marks the boundary between the two partitions.
Under the Hood: Tracing a Partition Step by Step
Take the array from Example 1, {10, 7, 8, 9, 1, 5}, and trace the first Lomuto partition() call with low = 0, high = 5:
- Pivot is
arr[5] = 5. Start withi = -1. j = 0:arr[0] = 10, not less than 5 — skip.j = 1:arr[1] = 7, not less than 5 — skip.j = 2:arr[2] = 8, not less than 5 — skip.j = 3:arr[3] = 9, not less than 5 — skip.j = 4:arr[4] = 1, less than 5 — incrementito 0 and swaparr[0]witharr[4]. Array becomes{1, 7, 8, 9, 10, 5}.- Loop ends. Swap
arr[i + 1] = arr[1]witharr[high] = arr[5]: array becomes{1, 5, 8, 9, 10, 7}. partition()returns1— the pivot value 5 is now at index 1, its correct final sorted position.
Quicksort then recurses on {1} (indices 0..0, already sorted) and on {8, 9, 10, 7} (indices 2..5), repeating the same process until every sub-array shrinks to size 0 or 1. Notice that only one element — the pivot — is guaranteed to reach its final position per partition call; everything else may still move again in a later recursive call.
Common Mistakes
Mistake 1: Off-by-one recursion bounds with the wrong partition scheme. Mixing up the recursive calls between schemes is a very common bug. Lomuto’s partition returns the pivot’s own index, so the correct recursive calls are quicksort(arr, low, pi - 1) and quicksort(arr, pi + 1, high). Hoare’s partition does not return the pivot’s index, so using pi - 1 / pi + 1 with Hoare’s scheme causes infinite recursion or an incorrect sort. Hoare’s correct calls are quicksort(arr, low, pi) and quicksort(arr, pi + 1, high), as shown in Example 3.
/* WRONG: using Lomuto-style bounds with hoarePartition() */
int pi = hoarePartition(arr, low, high);
quicksort(arr, low, pi - 1); /* can skip an element or recurse forever */
quicksort(arr, pi + 1, high);Mistake 2: Picking a bad pivot on already-sorted or reverse-sorted data. Always choosing the first or last element as the pivot is simple, but on an array that is already sorted (or sorted in reverse), every partition call puts the pivot at one extreme end, so one side of the split is always empty. Recursion depth grows to O(n) and running time degrades to O(n²) — the same as bubble sort, but with extra function-call overhead on top. This is exactly why real-world quicksort implementations avoid a fixed pivot position:
/* Naive: vulnerable to O(n^2) on sorted input */
int pivot = arr[high];
/* Better: pick the middle element, or better yet a
median-of-three (first, middle, last) or random index,
then swap it into the "high" position before partitioning. */
int mid = low + (high - low) / 2;
swap(&arr[mid], &arr[high]);
int pivot = arr[high];Mistake 3: Forgetting the base case guard, or using the wrong comparison. The recursive calls must be guarded with if (low < high). Without it (or with low <= high), the function keeps recursing even on empty or single-element ranges, and can index out of bounds or recurse forever, eventually crashing with a stack overflow.
Best Practices
- Prefer a smarter pivot choice — median-of-three (comparing the first, middle, and last elements) or a randomly chosen index — to avoid the O(n²) worst case on sorted or adversarial input.
- For small sub-arrays (typically fewer than 10–20 elements), switch to insertion sort; it has lower constant overhead and avoids the cost of recursive calls for tiny ranges. This hybrid approach is what most production-quality quicksort implementations use.
- Recurse into the smaller partition first and loop (rather than recurse) into the larger one; this bounds the call stack depth to O(log n) even in bad cases, an optimization often called tail-call elimination.
- Remember that quicksort is not stable. If you need to preserve the relative order of equal elements (e.g., sorting a list of records by one field while keeping ties in original order), use a stable algorithm like merge sort, or add a secondary tie-breaking key.
- For production code, prefer the standard library’s
qsort()from<stdlib.h>unless you have a specific reason to hand-roll your own — it is well-tested and typically well-optimized. - Always test your quicksort against edge cases: an empty array, a single-element array, an array with all equal elements, and an already-sorted array — these are exactly where naive implementations fail or perform poorly.
Practice Exercises
- Exercise 1: Modify Example 1 so that
partition()picks the middle element of the range as the pivot (swap it into thehighposition first, then partition as usual). Test it on the array{5, 5, 5, 5, 5}and confirm it still sorts correctly. - Exercise 2: Add a comparison counter (a global or pointer-passed
int) to Example 1 that counts how many timesarr[j] < pivotis evaluated. Run it on a random array of 10 elements versus an already-sorted array of 10 elements and compare the counts — what does this tell you about pivot choice? - Exercise 3: Rewrite Example 2 to sort an array of
struct { char name[20]; int score; }records byscorein descending order, using the Lomuto scheme from Example 1 as a starting point.
Summary
- Quicksort sorts in place using divide-and-conquer: pick a pivot, partition the array around it, then recursively sort each side.
- Average time complexity is O(n log n); worst case is O(n²), typically triggered by a poor pivot choice on already-sorted or adversarial data.
- The Lomuto scheme is simpler to understand and returns the pivot’s exact final index; the Hoare scheme is usually faster but requires different recursive bounds.
- Quicksort is unstable — equal elements can be reordered — and uses O(log n) extra memory for recursion, not O(n).
- Use median-of-three or random pivot selection, and fall back to insertion sort for small sub-arrays, to make quicksort robust in practice.
