Offensive Security Researcher & Quantum Cryptography Analyst

QuickSort Algorithm: Comprehensive Guide with Mathematical Analysis and C Implementation

Abdul Wahab Junaid
QuickSort: Comprehensive Guide with Mathematical Analysis and C Implementation

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

How It Works

I follow these steps for standard QuickSort:

  1. If the subarray has fewer than 2 elements, it’s already sorted — this is the recursive base case.
  2. Choose a pivot element from the subarray (I use the last element in my implementation).
  3. 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.
  4. Recursively apply QuickSort to the subarray of elements before the pivot.
  5. Recursively apply QuickSort to the subarray of elements after the pivot.
  6. 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:

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:

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

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

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

Space Complexity

QuickSort sorts in-place, requiring no auxiliary array for the data itself. However, it does consume stack space for recursion:

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

Disadvantages

Applications

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

Common Mistakes

Further Reading

Exit mobile version