Sorting Algorithms

It’s tempting to think of sorting as a “solved problem” — every standard library has a sort function, so why dwell on it? The honest answer is that sorting is the single richest case study in all of algorithm design: it’s a problem simple enough to state in one sentence, yet deep enough that decades of research have produced a whole family of genuinely different solutions, each one optimal under some set of assumptions and disastrous under others. Understanding why there isn’t one best sorting algorithm — and which assumptions make which algorithm the right choice — will teach you more about algorithmic thinking than almost any other single topic. And practically: an enormous number of problems become easy once their input is sorted (search, deduplication, finding medians and percentiles, grouping equal items, detecting collisions) — which is exactly why sorting shows up, explicitly or as a hidden first step, almost everywhere.

Defining the Problem (Precisely)

Sorting takes a sequence of n comparable items and rearranges them into non-decreasing order. That sounds complete, but two properties — easy to overlook, and the source of real bugs when ignored — distinguish sorting algorithms from one another just as much as their running time does:

• Stability: a sort is stable if it preserves the relative order of elements that compare as equal. Sort a list of students by grade, and a stable sort guarantees that students with the same grade stay in whatever order they were in before (say, alphabetical) — an unstable sort might shuffle them. Whether you need this depends entirely on whether you’ll ever sort by one key after already having sorted by another — a surprisingly common real-world pattern.
• In-place vs. extra space: an in-place sort rearranges the input using O(1) extra memory (beyond the input itself); others need O(n) auxiliary storage to do their work. On a server sorting gigabytes of data, that difference can be the difference between fitting in memory and not.

Keep both properties in mind as you meet each algorithm below — they are exactly the kind of “fine print” that separates a textbook description from a production-quality decision.

The Quadratic Family: Simple, Slow, and Surprisingly Useful

Three algorithms are usually taught first because they are the most direct translations of “how a person might sort a small pile of cards by hand” into code. All three are O(n²) in the worst case — and all three remain genuinely useful in specific corners of real systems, which is worth understanding rather than dismissing.

Bubble Sort

Repeatedly scan the array, swapping any adjacent pair that’s out of order. Each full pass guarantees that the largest remaining element “bubbles up” to its correct final position.

#include <stdbool.h>

void bubble_sort(int arr[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        bool swapped = false;
        for (int i = 0; i < n - 1 - pass; i++) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;                      /* nothing moved this pass: already sorted */
        }
    }
}

The swapped flag is not a cosmetic detail — it’s the difference between an algorithm that is always Θ(n²) and one that is O(n) on already-sorted input. Always ask, of any algorithm you study: “what happens to this on the easiest possible input — and does the code actually notice?”

Selection Sort

Repeatedly find the minimum of the unsorted remainder and swap it into place at the front.

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

Selection sort makes at most n - 1 swaps, total — full stop, regardless of the input. That’s a genuinely useful guarantee when each swap is expensive (imagine sorting massive records by moving whole blocks of memory, where comparisons are cheap but moves are costly). But notice it always scans the entire unsorted remainder to find the minimum, even if the array is already sorted — unlike bubble sort, it has no way to notice and stop early. It is also not stable (convince yourself with a small example: [3a, 3b, 1], where 3a and 3b are equal but distinguishable — trace the swaps and see which one ends up first).

Insertion Sort

Build up the sorted region one element at a time: take the next element from the unsorted part, and slide it leftward into its correct position within the already-sorted prefix.

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];        /* shift larger element rightward */
            j--;
        }
        arr[j + 1] = key;               /* drop key into the gap we made */
    }
}

This is the one quadratic sort that genuinely deserves a place in serious code, for a reason that rewards careful thought: its running time is proportional to the number of inversions in the input — pairs of elements that are out of order relative to each other. An array that’s already sorted has zero inversions, and insertion sort runs in O(n). An array that’s “almost sorted” — say, each element is at most a few positions from its final resting place, a common pattern in real append-mostly data — has O(n) inversions, and insertion sort runs in O(n) despite being “the O(n²) one.” This adaptiveness is precisely why production sorting routines (Python’s Timsort, Java’s Arrays.sort for objects) switch to insertion sort for small sub-arrays inside an otherwise much fancier algorithm — at small sizes, low overhead and adaptiveness beat asymptotically-superior-but-constant-heavy alternatives.

Pause and think: This is a second concrete instance of the warning from the Complexity Analysis chapter — “an O(n²) algorithm with small constants can beat an O(n log n) algorithm for realistic input sizes.” Here, the case is even sharper: insertion sort’s actual running time depends on a property of the input (the inversion count) that its O(n²) worst-case bound completely hides. A single Big-O number is a summary, and like any summary, it can erase exactly the detail you most need. When does a coarse summary mislead you, and when does it usefully focus your attention? That tension — between the clarifying power of abstraction and the information it necessarily throws away — is one you’ll meet again and again, far beyond algorithms.

Merge Sort: Guaranteed O(n log n), At a Price

You met the shape of merge sort in the previous chapter as the canonical divide-and-conquer example: split the array in half, recursively sort each half, then merge the two sorted halves into one. The part we deferred — the merge step — is where the real engineering lives:

#include <stdlib.h>

void merge(int arr[], int lo, int mid, int hi) {
    int n1 = mid - lo + 1;
    int n2 = hi - mid;
    int *left  = malloc(n1 * sizeof(int));
    int *right = malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) left[i]  = arr[lo + i];
    for (int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = lo;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {      /* <=, not <, is what makes this merge STABLE */
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < n1) arr[k++] = left[i++];   /* drain whichever side has leftovers */
    while (j < n2) arr[k++] = right[j++];

    free(left);
    free(right);
}

void merge_sort(int arr[], int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    merge_sort(arr, lo, mid);
    merge_sort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);
}

Merge sort’s defining trait is consistency: its running time is Θ(n log n) on every input — best, worst, and average case alike. There is no pathological input that degrades it, which is exactly the guarantee you want when correctness-under-adversarial-conditions matters (sorting data that an adversary might have deliberately crafted to attack your system, for instance — a real concern for anything exposed to the outside world). It is also naturally stable, provided you write the merge step’s tie-breaking comparison as <= rather than < — flip that one operator and you silently lose stability while the output remains “sorted.” That single-character difference is worth internalizing as a reminder of how easily a subtle correctness property can hide behind code that looks, and even tests as, perfectly fine.

The price for this consistency: merge sort needs O(n) auxiliary space for the temporary arrays, and is not in-place. (In-place merge algorithms exist, but they’re substantially more intricate and slower in practice — a textbook example of a trade-off where the “obviously better” property, using less memory, costs you enough elsewhere that it’s often not worth pursuing.)

Quicksort: Fast in Practice, Fragile in the Worst Case

Quicksort takes a different approach to divide and conquer: instead of splitting the array down the middle and doing the hard work in the combine step (as merge sort does), it does the hard work in the divide step — partitioning the array around a chosen pivot so that everything smaller ends up to its left and everything larger to its right — and then the combine step is free, because two independently-sorted halves with the pivot correctly placed between them is already a fully sorted whole.

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];                /* choosing the last element as pivot (Lomuto scheme) */
    int i = lo - 1;                     /* boundary of the "smaller than pivot" region */
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[hi]; arr[hi] = tmp;  /* place pivot in its final spot */
    return i + 1;                        /* the pivot's final index */
}

void quicksort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quicksort(arr, lo, p - 1);
        quicksort(arr, p + 1, hi);
    }
}

Why the Pivot Choice Is Everything

Trace through partition on an array that’s already sorted, always choosing the last element as the pivot. The largest element is always exactly where it belongs already — so the partition splits the array into a piece of size n - 1 and a piece of size 0, every single time. The recurrence becomes T(n) = T(n - 1) + O(n), which solves to Θ(n²) — quicksort’s worst case, triggered by what looks like the friendliest possible input.

Pause and think: This is the single most important fact to internalize about quicksort, and it directly answers the question left dangling at the end of the “best/worst/average case” discussion in the Complexity Analysis chapter — when does an average-case analysis actually change an algorithm’s behavioral class, rather than just its constant? Here is the answer in its sharpest form: quicksort’s worst case is Θ(n²), but if the pivot is chosen so that it lands anywhere in the middle 50% of the array (not even close to the median — just not near either extreme), the recursion depth is O(log n) and the total cost is Θ(n log n). Averaged over all possible pivot positions, “landing somewhere reasonable” is overwhelmingly the typical outcome — which is why quicksort’s average case is Θ(n log n) and, in practice, frequently outperforms merge sort despite having a theoretically worse worst case. The gap between “what adversarial input can do to you” and “what typical input actually does” is not a footnote here — it is the entire reason this algorithm is famous.

This also explains why production implementations never pick a fixed position (first, last, or middle element) as the pivot: doing so makes the worst case triggerable on purpose — by sorted input, reverse-sorted input, or any input an adversary can predict your pivot rule from. Common mitigations include choosing the median of three candidate elements (e.g. first, middle, last), or picking a random element — which doesn’t change the worst-case bound (an adversary with enough patience can still get unlucky with you) but makes that worst case occur with vanishingly small probability on any input fixed in advance, which is a guarantee you can actually build a system around.

Try it yourself: Modify partition to first swap a randomly chosen element into the arr[hi] position before partitioning around it (you’ll need <stdlib.h>’s rand()). Then construct, by hand, an input that reliably triggers Θ(n²) behavior in the original fixed-pivot version — and confirm that your randomized version no longer reliably misbehaves on that same input. What has changed: the worst case itself, or merely your ability to predict when it will strike?

Heapsort: Merge Sort’s Guarantee, In Place

Is there an algorithm with merge sort’s ironclad Θ(n log n) worst-case guarantee and quicksort’s O(1) extra space? Yes — heapsort, and it gets there by leaning on a data structure rather than a cleverer recursive split. (If the heap isn’t yet familiar, the Data Structures course covers it in depth — but the core fact you need is this: a max-heap is a binary tree, stored compactly in a plain array, with the property that every parent is greater than or equal to its children — which means the maximum element is always sitting at the root, retrievable in O(1).)

The algorithm has exactly two phases: build a max-heap out of the entire array (O(n), surprisingly — not O(n log n), for reasons that reward a careful look at the math, but which we won’t detour into here), then repeatedly swap the root (the maximum) with the last element of the unsorted region, shrink that region by one, and restore the heap property by sifting the new root downward.

void sift_down(int arr[], int heap_size, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left  < heap_size && arr[left]  > arr[largest]) largest = left;
    if (right < heap_size && arr[right] > arr[largest]) largest = right;

    if (largest != root) {
        int tmp = arr[root]; arr[root] = arr[largest]; arr[largest] = tmp;
        sift_down(arr, heap_size, largest);    /* the swap may have broken the property further down */
    }
}

void heap_sort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {      /* heapify: sift down every internal node, bottom-up */
        sift_down(arr, n, i);
    }
    for (int end = n - 1; end > 0; end--) {
        int tmp = arr[0]; arr[0] = arr[end]; arr[end] = tmp;   /* move current max to its final slot */
        sift_down(arr, end, 0);                                /* restore the heap on the shrunken region */
    }
}

Notice the elegant symmetry with selection sort: both algorithms repeatedly extract the maximum (or minimum) of an unsorted region and place it at the boundary. The entire difference — and it’s an enormous one — is how they find that maximum. Selection sort scans linearly, in O(n), every single time. Heapsort maintains a structure that hands over the maximum in O(1) and can be repaired in O(log n), turning the same basic strategy from Θ(n²) into Θ(n log n). The algorithm’s “shape” didn’t change; the data structure underneath it did — and that alone was the entire improvement. This is one of the most important lessons a developing problem-solver can internalize: sometimes the path to a faster algorithm isn’t a cleverer sequence of steps, but a smarter structure that makes an expensive step cheap.

Heapsort is not stable (sifting can reorder equal elements arbitrarily) and, despite its excellent guaranteed complexity, tends to have worse real-world constants than a well-tuned quicksort, due to less cache-friendly memory access patterns — yet another reminder that the gap between “asymptotically optimal” and “fastest in practice” is real, measurable, and often decided by the hardware underneath your code.

Comparing the Comparison Sorts

* Quicksort’s “space” row counts the recursion stack, not auxiliary arrays — a subtlety worth noticing on its own: a sort can be “in-place” with respect to the data it’s rearranging while still consuming non-trivial memory through its call stack, which is exactly the kind of detail the previous chapter’s discussion of recursive space cost prepared you to spot.

How Slow Must Sorting Be? The Comparison Lower Bound

Here’s a question that sounds almost philosophical but has a sharp, satisfying answer: is there a comparison-based sorting algorithm that beats O(n log n) — say, one that runs in O(n)? The surprising answer is no, and the proof is one of the most elegant arguments in all of computer science, because it doesn’t analyze any particular algorithm — it proves something about every possible algorithm of a certain kind, all at once.

Any comparison sort can be modeled as a decision tree: each internal node represents one comparison (is arr[i] < arr[j]?), each branch represents one possible outcome, and each leaf represents one fully-determined output ordering. To correctly sort every possible input arrangement of n distinct elements, the tree must have at least n! leaves — one for each possible permutation, since the algorithm must be able to distinguish any one arrangement from any other and produce the right answer for each. A binary tree with L leaves must have height at least log₂ L (you cannot fit more leaves into a tree than 2^height). Therefore the height of this decision tree — which corresponds exactly to the worst-case number of comparisons the algorithm might need to make — is at least log₂(n!). Using Stirling’s approximation, log₂(n!) = Θ(n log n).

No amount of cleverness in how you choose what to compare can escape this bound, because the argument never assumed anything about the algorithm’s strategy — only that it sorts by comparing pairs of elements and must get every input right. This is a genuinely different kind of result from the upper-bound analyses you’ve done so far: it’s not “here is an algorithm and here is how fast it runs,” it’s “here is a mathematical ceiling that no algorithm of this type can break through, ever, on any machine, written in any language.” Lower-bound arguments like this one are how we know, with certainty, when to stop looking for a faster comparison sort and start asking a different question instead.

Pause and think: That final sentence contains a trapdoor — “a comparison sort.” The lower bound’s entire proof leaned on the assumption that the only thing the algorithm can do with two elements is compare them and branch on the result. What if that assumption is false — what if you know something more about your data than “it supports <”? Hold that thought; it’s about to pay off spectacularly.

Escaping the Bound: Sorting Without Comparing

If you know more about your data than just “it’s comparable” — for instance, that it consists of integers drawn from a small, known range — you can sort without ever comparing two elements to each other, and the Ω(n log n) lower bound, which applies only to comparison-based algorithms, simply does not constrain you.

Counting Sort

Suppose every element is an integer between 0 and some known maximum k. Count how many times each value occurs; turn those counts into a running total (a prefix sum), which directly tells you how many elements are less than or equal to any given value — and therefore exactly which output position each element belongs in.

#include <stdlib.h>

void counting_sort(int arr[], int n, int max_value) {
    int *count  = calloc(max_value + 1, sizeof(int));
    int *output = malloc(n * sizeof(int));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;                          /* tally occurrences of each value */
    }
    for (int v = 1; v <= max_value; v++) {
        count[v] += count[v - 1];                  /* running total: count[v] = "how many <= v" */
    }
    for (int i = n - 1; i >= 0; i--) {              /* iterate backwards: this is what makes it STABLE */
        output[--count[arr[i]]] = arr[i];
    }
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
}

This runs in Θ(n + k) — genuinely linear when k = O(n). It directly sidesteps the comparison lower bound by never asking “is x less than y?” — instead, it asks “exactly how many things are less than or equal to x?” and uses the answer to compute a destination index directly. This is the trapdoor the lower bound left open: a fundamentally different kind of operation, unavailable to a pure comparison sort, that makes a fundamentally different complexity achievable.

The catch is right there in the bound, Θ(n + k): if the range k is huge relative to n — sorting a million 64-bit numbers, say — counting sort needs an array with quintillions of slots, and is hopelessly impractical. It trades the assumption “comparable” for the much stronger assumption “small integer range,” and is only a good idea exactly when that stronger assumption genuinely holds.

Try it yourself: Trace through the third loop of counting_sort by hand on the tiny input arr = [3, 1, 3, 2]. Pay close attention to why iterating backwards (i = n - 1 down to 0) — rather than forwards — is what guarantees that two equal elements end up in the same relative order they started in. (This is a wonderful, compact illustration of how a seemingly arbitrary implementation choice — loop direction — can be the entire difference between a stable algorithm and an unstable one. Try the forward version and find an input where it visibly breaks stability.)

Radix Sort

What if your integers don’t fit in a small range — but they do have a bounded number of digits? Radix sort sorts by individual digits (or fixed-width chunks of bits), from the least significant to the most significant, using a stable sort — typically counting sort, restricted to the 10 (or however many) possible digit values — as a subroutine at each pass:

Sort [170, 45, 75, 90, 802, 24, 2, 66] by ones digit:  [170, 90, 802, 2, 24, 45, 75, 66]
Then by tens digit (stable!):                          [802, 2, 24, 45, 66, 170, 75, 90]
Then by hundreds digit (stable!):                      [2, 24, 45, 66, 75, 90, 170, 802]

Why does sorting digit-by-digit, from least to most significant, produce a fully sorted result? This is worth pausing on, because the answer is a small masterpiece of inductive reasoning: after the pass on the ones digit, any two numbers with different ones digits are correctly ordered relative to each other. The pass on the tens digit then groups numbers by their tens digit while preserving that relative order for numbers that tie on the tens digit — which is exactly what a stable sort guarantees. By induction, after processing all d digit positions, any two numbers are correctly ordered: either they differ in some digit position (and the pass over that position placed them correctly, and no later pass disturbed that, because later passes only reorder numbers that are equal in the more-significant digits being considered) or they’re equal in every position (and so their relative order — whatever it originally was — is exactly what a fully “tied” comparison should preserve).

Pause and think: That entire argument collapses if the per-digit sort isn’t stable — try to construct a small example (three or four two-digit numbers) where using an unstable sort for the per-digit passes produces a final result that isn’t fully sorted. Stability, which might have looked like a nice-to-have footnote back when we first defined it, turns out to be the single load-bearing property that makes radix sort correct at all — not merely “nicer,” but the difference between an algorithm and a non-algorithm. This is a good moment to revisit your mental filing of “stability” from “minor implementation detail” to “sometimes the entire ballgame,” and to start asking, of every property you’re tempted to skim past in a definition: what would break if this weren’t true?

Radix sort runs in Θ(d · (n + k)), where d is the number of digits and k is the base (e.g. 10 for decimal digits, or 256 for byte-wise passes on binary data). When d is small and fixed — sorting fixed-width integers, IP addresses, or fixed-length strings — this is effectively Θ(n), again entirely outside the reach of the comparison-sort lower bound, for exactly the same fundamental reason counting sort was: it never asks “which is bigger,” only “which bucket does this belong in.”

Choosing a Sort: A Decision Framework

Faced with a real sorting task, work through these questions in order — they will, almost always, lead you straight to the right choice:

1. Do I know more about my data than “it’s comparable”? Small integer range → counting sort. Fixed-width keys (integers, short strings) → radix sort. If the answer is genuinely “no, all I have is a comparison” — proceed to the next questions; you’re bound by the Ω(n log n) wall, and your job is to pick the comparison sort with the best constants and properties for your situation.
2. Do I need a stability guarantee — will I ever sort by a secondary key after a primary one, or otherwise rely on “ties keep their original order”? If yes, that rules out plain quicksort and heapsort (or demands a stable variant of them, which exist but cost more).
3. Can I afford O(n) extra memory, or must the sort be in-place? Memory-constrained environments (embedded systems, huge datasets that barely fit in RAM) push toward quicksort or heapsort; if memory is comfortable, merge sort’s consistency becomes very attractive.
4. Is my data adversarial, or could it be? Anything that processes data from outside your control — user uploads, network input, anything an attacker might shape on purpose — should avoid plain quicksort’s exploitable worst case, or must use randomization or a worst-case-safe fallback.
5. Is my data already mostly sorted, or likely to be small? Insertion sort, unglamorous as it looks on paper, may genuinely be your best choice — which is exactly why every serious general-purpose sort in wide use today is a hybrid: Timsort (Python, Java) is fundamentally a merge sort that switches to insertion sort for small runs; introsort (C++‘s std::sort) starts with quicksort, falls back to heapsort if the recursion gets suspiciously deep (a built-in defense against the Θ(n²) worst case), and finishes small partitions with insertion sort. The “best” sorting algorithm in production is rarely any single algorithm from this chapter — it’s a considered combination of several, each covering for the others’ weaknesses. That, more than any individual algorithm, is the real lesson sorting has to teach about engineering.

Bringing It Together: Practice as a Problem-Solver

1. Count the cost, concretely. For an array of n = 8 elements, compute the exact number of comparisons bubble sort, selection sort, and insertion sort each make on the input [8, 7, 6, 5, 4, 3, 2, 1] (worst case for all three) and on [1, 2, 3, 4, 5, 6, 7, 8] (best case for some, worst for others). Which algorithm’s behavior surprises you most across the two inputs, and why?

2. Break it on purpose. Construct a 16-element input that forces the fixed-last-element-pivot quicksort above into its Θ(n²) worst case, and trace through enough of the recursion to convince yourself it really does degrade the way the analysis predicts. Then describe, in one sentence, the general shape of input that triggers this — and explain why median-of-three pivot selection defeats your specific construction (and why an adversary who knows you’re using median-of-three could, in principle, construct a new attack against it too).

3. Design challenge. You need to sort a list of about ten million student records by final exam score, where scores are integers from 0 to 100, and you also need students with tied scores to retain their original roll-number order. Walk through the decision framework above, step by step, and arrive at a specific algorithm choice — including which specific variant and why. Then do the same for a second scenario: sorting a few hundred arbitrary user-submitted strings by length, where the strings might be adversarially crafted by someone trying to make your program slow. Compare your two answers — what changed, and which single factor most influenced the change?

4. Reflection. Heapsort achieved merge sort’s worst-case guarantee without merge sort’s extra memory, by swapping in a smarter data structure rather than a smarter algorithmic shape. Look back at the summarize example from the Complexity Analysis chapter, where an O(k) membership scan was the bottleneck — and the hint pointed toward a structure that could do that check in O(1). Notice the common thread: in both cases, the fix wasn’t “write cleverer logic,” it was “store the data in a shape that makes the operation you need cheap.” As you continue through this course (and especially once you reach the Data Structures material, if you haven’t already), make a habit of asking — for any algorithm that feels slower than it should — “is the bottleneck in what I’m doing, or in what shape my data is in while I do it?” That single question, asked at the right moment, is behind a remarkable fraction of the biggest performance breakthroughs in real software.