QuickSort is the algorithm I reach for most often when I need a fast, general-purpose, in-place sort, and it’s usually the first “real” divide-and-conquer algorithm I recommend to anyone learning algorithms after Merge Sort. What draws me to it is the contrast between its beautifully simple idea — pick a pivot, partition around it, recurse — and the surprisingly rich mathematical analysis needed to understand why it performs so well in practice despite a worst case that looks alarming on paper.
In this article, I want to walk through QuickSort from its history all the way to a tested C implementation, spending real time on the mathematics that explains its $O(n \log n)$ average-case behavior.
History and Background
QuickSort was invented by Tony Hoare in 1959, while he was a visiting student at Moscow State University working on a machine translation project. I find this origin story remarkable — Hoare needed to sort words to look them up in a Russian-to-English dictionary efficiently, and the constraints of that specific translation problem led him to design what has become one of the most widely used sorting algorithms in the history of computing. He published the algorithm formally in 1961 in The Computer Journal.
Hoare’s original partitioning scheme (now called the Hoare partition scheme) differs slightly from the more commonly taught Lomuto partition scheme, which I use in my implementation below because I find it more intuitive to explain, even though Hoare’s original version is generally more efficient in practice. Over the following decades, QuickSort became a staple of standard libraries — many qsort implementations in C, and sorting routines in various runtime libraries, are directly descended from Hoare’s algorithm, often combined with additional optimizations like switching to Insertion Sort for small subarrays or using median-of-three pivot selection.
Problem Statement
The problem I’m solving is the general sorting problem: given an array of $n$ comparable elements, rearrange them into non-decreasing order. QuickSort belongs to the comparison-based sorting family, meaning it only gains information about element order through pairwise comparisons — which places it under the $\Omega(n \log n)$ worst-case lower bound that applies to all such algorithms.
What makes QuickSort distinct from Merge Sort is how it divides the problem: instead of splitting the array at its midpoint, it partitions the array around a chosen pivot value, so that everything smaller ends up on one side and everything larger ends up on the other.
Core Concepts
- Pivot: An element chosen from the array around which the rest of the elements are partitioned.
- Partitioning: The process of rearranging the array so that elements less than or equal to the pivot appear before it, and elements greater appear after it, with the pivot landing in its final sorted position.
- In-place sorting: QuickSort sorts the array using only a small amount of extra memory (used for recursion), without needing a separate output array like Merge Sort does.
- Divide-and-conquer: A strategy where a problem is broken into smaller subproblems (partitions), solved recursively, and then combined — though for QuickSort, the “combining” step is trivial since partitioning already leaves the array correctly arranged relative to the pivot.
- Lomuto partition scheme: The specific partitioning method I use in my implementation, which selects the last element as the pivot and uses a single index to track the boundary of the “smaller than pivot” region.
How It Works
I follow these steps for standard QuickSort:
- If the subarray has fewer than 2 elements, it’s already sorted — this is the recursive base case.
- Choose a pivot element from the subarray (I use the last element in my implementation).
- Partition the subarray: rearrange elements so everything less than or equal to the pivot comes before it, and everything greater comes after it. The pivot now sits in its correct final sorted position.
- Recursively apply QuickSort to the subarray of elements before the pivot.
- Recursively apply QuickSort to the subarray of elements after the pivot.
- Once recursion completes on both sides, the entire array is sorted — there’s no explicit merge step needed.
Working Principle
The internal mechanism I rely on is the partitioning invariant. During partitioning, I maintain an index i that marks the boundary of the region known to be less than or equal to the pivot. As I scan through the array with index j, any time I find an element $\leq$ pivot, I increment i and swap it into position i. By the time j reaches the end, everything from the start up to index i is guaranteed to be $\leq$ pivot, and everything from i+1 to the second-to-last position is guaranteed to be $>$ pivot. A final swap places the pivot itself right between these two regions, in its correct sorted position.
This is what makes QuickSort’s recursive structure valid: after partitioning, I never need to compare elements across the pivot boundary again, because the partitioning step has already established their correct relative order.
Mathematical Foundation
I find QuickSort’s mathematical analysis to be one of the more rewarding derivations in algorithms.
Worst case: This occurs when the partition is maximally unbalanced — for example, when the pivot is always the smallest or largest element, which happens on already-sorted input with my last-element pivot choice. The recurrence is:
$$ T(n) = T(n-1) + T(0) + \Theta(n) $$
Solving this recurrence (essentially an arithmetic series) gives:
$$ T(n) = \Theta(n^2) $$
Best case: This occurs when the pivot always splits the array into two equal halves:
$$ T(n) = 2T(n/2) + \Theta(n) $$
By the Master Theorem (case 2, since $a=2$, $b=2$, and $f(n) = \Theta(n) = \Theta(n^{\log_b a})$):
$$ T(n) = \Theta(n \log n) $$
Average case: This is the more interesting derivation. Assuming a random pivot (or random input order), I can show that the expected running time is also $\Theta(n \log n)$. One elegant way I like to derive this uses indicator random variables to count the expected number of comparisons.
Let $X$ be the total number of comparisons performed by QuickSort. I define indicator random variables $X_{ij}$ for each pair of elements $z_i$ and $z_j$ (where $z_i$ is the $i$-th smallest element in the final sorted array):
$$ X = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} X_{ij} $$
A key insight is that $z_i$ and $z_j$ are compared if and only if one of them is chosen as a pivot before any element strictly between them (in sorted order) is chosen. Given a random pivot choice, this happens with probability:
$$ P(z_i \text{ compared to } z_j) = \frac{2}{j – i + 1} $$
Taking the expectation of $X$ using linearity of expectation:
$$ E[X] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j – i + 1} $$
This double sum can be shown (through substitution and bounding by the harmonic series) to evaluate to:
$$ E[X] = O(n \log n) $$
This confirms that, on average, QuickSort performs $O(n \log n)$ comparisons, even though its worst case remains $O(n^2)$.
Diagrams
Here is the overall recursive flow of QuickSort:
flowchart TD
A[Unsorted Subarray] --> B{Length less than 2?}
B -- Yes --> C[Already Sorted, Return]
B -- No --> D[Choose Pivot]
D --> E[Partition Around Pivot]
E --> F[Recursively Sort Left Partition]
E --> G[Recursively Sort Right Partition]
F --> H[Combined Array is Sorted]
G --> H
And here’s a diagram illustrating the Lomuto partitioning process for a single call:
flowchart LR
A["Start: i = low - 1, pivot = arr[high]"] --> B["Scan j from low to high - 1"]
B --> C{"arr[j] <= pivot?"}
C -- Yes --> D["i++, swap arr[i] and arr[j]"]
C -- No --> B
D --> B
B --> E["Swap arr[i+1] and arr[high]"]
E --> F["Pivot now at index i+1 (final position)"]Pseudocode
QUICKSORT(A, low, high)
if low < high
pivotIndex = PARTITION(A, low, high)
QUICKSORT(A, low, pivotIndex - 1)
QUICKSORT(A, pivotIndex + 1, high)
PARTITION(A, low, high)
pivot = A[high]
i = low - 1
for j = low to high - 1
if A[j] <= pivot
i = i + 1
swap A[i] and A[j]
swap A[i + 1] and A[high]
return i + 1
Step-by-Step Example
Let me trace through the array:
$$ [10, 7, 8, 9, 1, 5] $$
Call 1: QuickSort(arr, 0, 5), pivot = 5 (last element)
Scanning j from 0 to 4, comparing against pivot 5:
- $j=0$: 10 > 5, no swap
- $j=1$: 7 > 5, no swap
- $j=2$: 8 > 5, no swap
- $j=3$: 9 > 5, no swap
- $j=4$: 1 $\leq$ 5, so $i$ becomes 0, swap arr[0] and arr[4] → $[1, 7, 8, 9, 10, 5]$
Final swap: swap arr[1] and arr[5] (pivot position) → $[1, 5, 8, 9, 10, 7]$
Pivot 5 is now at index 1, its correct final position.
Call 2: QuickSort(arr, 0, 0) — single element, already sorted.
Call 3: QuickSort(arr, 2, 5), on subarray $[8, 9, 10, 7]$, pivot = 7 (last element)
Scanning j from 2 to 4, comparing against pivot 7:
- $j=2$ (value 8): 8 > 7, no swap
- $j=3$ (value 9): 9 > 7, no swap
- $j=4$ (value 10): 10 > 7, no swap
No swaps occurred, so $i$ stays at 1 (low – 1 = 1). Final swap: swap arr[2] and arr[5] → $[1, 5, 7, 9, 10, 8]$
Pivot 7 is now at index 2.
Call 4: QuickSort(arr, 3, 5), on subarray $[9, 10, 8]$, pivot = 8
- $j=3$ (value 9): 9 > 8, no swap
- $j=4$ (value 10): 10 > 8, no swap
Final swap: swap arr[3] and arr[5] → $[1, 5, 7, 8, 10, 9]$
Pivot 8 now at index 3.
Call 5: QuickSort(arr, 4, 5), on subarray $[10, 9]$, pivot = 9
- $j=4$ (value 10): 10 > 9, no swap
Final swap: swap arr[4] and arr[5] → $[1, 5, 7, 8, 9, 10]$
The array is now fully sorted, matching exactly what my tested C implementation produces.
Time Complexity
- Best Case: $O(n \log n)$ — occurs when partitioning is always balanced.
- Average Case: $O(n \log n)$ — proven through the indicator random variable analysis above, assuming random pivot selection or random input order.
- Worst Case: $O(n^2)$ — occurs on already-sorted (or reverse-sorted) input when always choosing the first or last element as pivot, since each partition splits off only a single element.
Space Complexity
QuickSort sorts in-place, requiring no auxiliary array for the data itself. However, it does consume stack space for recursion:
- Best/Average Case: $O(\log n)$ recursive stack depth, since partitions are roughly balanced.
- Worst Case: $O(n)$ recursive stack depth, since each recursive call may only shrink the problem by one element.
This makes QuickSort’s practical space usage significantly better than Merge Sort’s $O(n)$ auxiliary array requirement, which is part of why I often prefer QuickSort when memory is constrained.
Correctness Analysis
I verify correctness through two properties, proven inductively:
Partition correctness: After each call to PARTITION, I can show that every element in $A[low..i]$ is $\leq$ pivot, and every element in $A[i+2..high]$ is $>$ pivot, and the pivot itself sits at $A[i+1]$. This follows directly from the loop invariant maintained during the scan — at the start of each iteration of the for loop, this partial partitioning property already holds for the elements examined so far.
Recursive correctness: Assuming (inductively) that QUICKSORT correctly sorts any array of size smaller than $n$, I know both recursive calls correctly sort their respective partitions. Combined with the partition correctness guarantee (that everything in the left partition is $\leq$ pivot $\leq$ everything in the right partition), the overall array must be sorted once both recursive calls complete.
The base case (low >= high, meaning 0 or 1 elements) is trivially sorted, which anchors the induction.
Advantages
- Excellent average-case performance, $O(n \log n)$, with low constant factors in practice — often faster in real-world benchmarks than Merge Sort or Heap Sort.
- Sorts in-place, requiring only $O(\log n)$ additional space in typical cases.
- Cache-friendly due to its sequential, local partitioning access pattern.
- Easily randomized (random pivot selection) to make worst-case behavior extremely unlikely on any given input.
Disadvantages
- Worst-case time complexity of $O(n^2)$, which can be triggered by adversarial or already-sorted input if pivot selection is naive.
- Not stable by default — equal elements may not preserve their original relative order.
- Recursive implementation can hit stack depth issues on already-sorted or reverse-sorted large inputs unless randomization or tail-call optimization is applied.
- Performance is sensitive to pivot selection strategy, requiring care (median-of-three, random pivot) to avoid pathological cases.
Applications
- General-purpose sorting in standard libraries — many
qsort-style implementations across languages are based on QuickSort or hybrids like Introsort. - Used inside more advanced hybrid algorithms, such as Introsort, which switches to Heap Sort when recursion depth exceeds a threshold to guarantee $O(n \log n)$ worst-case behavior.
- Selection algorithms: a variant of QuickSort’s partitioning step (Quickselect) is used to find the $k$-th smallest element in expected linear time.
- Any performance-critical sorting task where average-case speed and in-place memory usage matter more than worst-case guarantees or stability.
Implementation in C
Here is my tested implementation using the Lomuto partition scheme:
#include <stdio.h>
// Swaps two integers via pointers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Lomuto partition scheme: uses the last element as pivot
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1; // boundary of the "less than or equal to pivot" region
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
// Place the pivot in its correct final position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// Recursively sorts arr[low..high]
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 n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Before sorting: ");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("After sorting: ");
printArray(arr, n);
return 0;
}
Sample Input and Output
Input:
10 7 8 9 1 5
Output (verified by compiling and running the code above):
Before sorting: 10 7 8 9 1 5
After sorting: 1 5 7 8 9 10
Optimization Techniques
- Randomized pivot selection: Choosing a random element as the pivot (swapping it to the end before partitioning) makes the worst case extremely unlikely regardless of input arrangement.
- Median-of-three pivot selection: Choosing the median of the first, middle, and last elements as the pivot tends to produce more balanced partitions than a fixed choice.
- Switching to Insertion Sort for small subarrays: Since Insertion Sort has lower constant-factor overhead for small $n$, many practical implementations switch to it once the subarray size drops below a threshold (commonly around 10-20 elements).
- Tail-call elimination: Converting one of the two recursive calls into a loop (recursing on the smaller partition, looping on the larger) bounds the stack depth to $O(\log n)$ even in unbalanced cases.
- Three-way partitioning (Dutch national flag): For arrays with many duplicate keys, partitioning into “less than,” “equal to,” and “greater than” pivot regions avoids repeatedly re-partitioning equal elements.
Common Mistakes
- Always choosing the first or last element as pivot on data that might be sorted or reverse-sorted, triggering the $O(n^2)$ worst case unnecessarily.
- Off-by-one errors in the partition boundaries, especially around the
low,high, andiindex management in the Lomuto scheme. - Forgetting the final swap that places the pivot into its correct position after the scanning loop completes.
- Assuming QuickSort is stable — using it in contexts where preserving the relative order of equal elements matters, without accounting for its instability.
- Not handling recursion depth on very large, adversarial inputs, leading to stack overflow in naive recursive implementations without tail-call optimization or hybrid fallback.
Further Reading
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), MIT Press — https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- C.A.R. Hoare, “Quicksort”, The Computer Journal, 1962 — https://academic.oup.com/comjnl/article/5/1/10/395338
- Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching — https://www-cs-faculty.stanford.edu/~knuth/taocp.html
- Wikipedia, “Quicksort” — https://en.wikipedia.org/wiki/Quicksort
- Visualgo, Sorting Visualization — https://visualgo.net/en/sorting
