Sorting Algorithms: Merge Sort, Quicksort, and Why a Bad Pivot Costs You O(n²)

You’re dealt a hand of cards and, without being told to, you start tidying them. You slide the 7 left until it sits after the 5. You pluck the jack out and push it toward the other face cards. Card by card, a mess becomes an order — and you never once thought about how you were doing it. Your hands just knew.

That quiet instinct is an entire branch of computer science. Sorting is the most-studied problem in the field, and the reason is worth saying out loud: an ordered list unlocks everything else. Binary search needs it. Deduplication, median-finding, merging, grouping — all get easy the moment the data is in order. By the end of this article you and I will have built the two sorts that matter most, merge sort and quicksort, watched a careless pivot blow one of them up from O(n log n) to O(n²), and understood the deep reason no comparison sort can ever beat O(n log n).

Let’s start nowhere near a computer

Stay with the hand of cards, because it holds the first algorithm whole.

Here’s the trick your hands already use. Keep the left side of your hand sorted at all times. Draw the next card and slide it leftward — past every card bigger than it — until it meets one that isn’t, and drop it there. The sorted part grows by one; the unsorted part shrinks by one. Repeat until there’s nothing left to draw.

That’s insertion sort, and it has a lovely property you can feel in your hands: if the cards are already almost in order, each one barely moves — a slot or two — and you’re done in a single flick down the hand. Hand it a shuffled deck, though, and every card might slide all the way across, which is where the cost hides. We’ll pin that cost down in a moment.

Now a second card trick, because it seeds the other half of the article. Suppose two friends each hand you a small pile that’s already sorted, and you want one merged sorted pile. You don’t re-sort anything. You look only at the top card of each pile, take the smaller, and repeat. Two piles of ten collapse into one pile of twenty in twenty glances. Hold onto that move — merging two sorted piles is cheap — because it’s the engine of the fastest sort we’ll build.

Where you already meet it

Once you notice sorting, it’s the substrate under half your day. Your email is a sort by time. Your contacts are a sort by name. A leaderboard is a sort by score, a file browser a sort by size-or-date you toggle with a click, a store’s “price: low to high” a sort you asked for by name.

But the most instructive place is the humblest: a spreadsheet. Say you have a table of orders and you sort it by customer name. Then you sort that same table by date. Watch what a good spreadsheet does — within each date, the rows stay in name order from your first sort. You got a two-level sort (date, then name) for free, just by sorting twice, cheapest key last.

That only works because the sort is stable: when two rows tie on the key you’re sorting by, it never gratuitously reorders them — it preserves the order they already had. Break that promise and your second sort scrambles the first, and the free two-level ordering evaporates. Stability is the quiet feature you never think about until a sort silently shuffles your ties and a report comes out wrong. We’ll come back to exactly which algorithms keep the promise and which don’t.

What it actually looks like

Before any code, here’s the shape of the fastest idea in sorting — divide and conquer. To sort an array, split it in half, sort each half, and merge the two sorted halves back together. The halves get sorted the same way: split, sort, merge, all the way down until a “half” is a single element, which is sorted by definition.

Read it top to bottom, then bottom to top. Going down, splitting is free — you just pick the midpoint; nothing is compared, nothing moves. Coming back up, every merge does real work, zipping two sorted runs into one. The whole cleverness of merge sort lives in that upward journey, so that’s where we’ll spend our time.

Let’s build one, step by step

We’ll build up from the simple-but-slow sort to the two fast ones, assembling the full code at the end.

Step 1 — the O(n²) family: insertion sort

The hand of cards you already sorted is insertion sort. Walk the array left to right; for each element, slide it back over the sorted prefix until it’s in place.

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {   // '>' (not '>=') leaves equals put → stable
            a[j + 1] = a[j];             // shift the bigger element one slot right
            j--;
        }
        a[j + 1] = key;                  // drop key into the gap that opened
    }
}

The rule: grow a sorted prefix one element at a time. The cost is all in that inner while. On a shuffled array, element i can slide back over all i earlier ones, so the work is 1 + 2 + … + (n−1), which is O(n²) — fine for a dozen items, ruinous for a million. Its sibling bubble sort (repeatedly swap adjacent out-of-order pairs) is the same O(n²) story with more swaps and no redeeming feature; insertion sort is strictly the one to know.

So why keep an O(n²) sort in your pocket at all? Because of that near-sorted magic. If the array is already almost in order, every element finds its home in a hop or two, the inner loop barely runs, and the whole thing finishes in O(n). That’s not a toy case — it’s why the fastest real-world sorts (Timsort, introsort) switch to insertion sort for small or nearly-sorted chunks. It’s the right tool precisely when the data is already gentle.

Step 2 — divide and conquer: merge sort’s split

Now the fast idea. Merge sort is the tree you saw above, written as a recursion: sort the left half, sort the right half, merge. The split itself is nothing but arithmetic.

private static void mergeSort(int[] a, int[] buf, int lo, int hi) {
    if (lo >= hi) {
        return;                          // a run of length 1 is already sorted
    }
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, buf, lo, mid);          // sort the left half
    mergeSort(a, buf, mid + 1, hi);      // sort the right half
    merge(a, buf, lo, mid, hi);          // zip the two sorted halves together
}

The rule: halve until trivial, then combine. Each level of the recursion halves the sub-array, so there are log₂ n levels — split a million down to singletons in about twenty splits. That mid = lo + (hi - lo) / 2 is the same overflow-safe midpoint from binary search: on a huge array, lo + hi could overflow a 32-bit int, so we add the half-width to lo instead. All that’s left is the merge.

Step 3 — the merge step, where the real work happens

This is the heart of merge sort, so let’s go slow. You have two sorted runs sitting side by side, and one scratch array to build the answer in. Put a finger on the head of each run. Compare the two heads, copy the smaller into the output, and advance that one finger. Repeat until a run runs dry, then pour the leftovers in.

private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[j] < a[i]) {               // strict '<': left wins ties → stable
            buf[k++] = a[j++];
        } else {
            buf[k++] = a[i++];
        }
    }
    while (i <= mid) {
        buf[k++] = a[i++];               // drain whatever is left in the left run
    }
    while (j <= hi) {
        buf[k++] = a[j++];               // ...or the right run
    }
    System.arraycopy(buf, lo, a, lo, hi - lo + 1);
}

Two things make this the crux of everything.

First, why it’s fast. Each comparison copies exactly one element into the output and advances one finger, so a merge of m total elements does m copies — it’s O(m), linear. Now sum that over the whole tree: each of the log n levels merges every element exactly once, so each level costs O(n), and the whole sort is O(n log n). That product — n work per level, log n levels — is the single most important cost equation in sorting, and it never degrades. Merge sort is O(n log n) on sorted input, reversed input, random input, adversarial input. There is no bad case.

Second, why it’s stable. Look at the tie: if (a[j] < a[i]). It only takes from the right run when the right head is strictly smaller. On a tie, the else fires and it takes from the left. Since the left run holds the elements that appeared earlier in the original array, equal elements come out in their original order — the stability promise, kept by one < instead of <=. This is the same discipline as insertion sort’s >, and it’s not an accident you can hand-wave: get the comparison backwards and merge sort silently becomes unstable.

Step 4 — quicksort: partition around a pivot

Quicksort flips the strategy. Instead of doing the work on the way up (merge), it does it on the way down (partition), and combines with nothing at all.

Pick one element as the pivot. Now rearrange the array so everything smaller than the pivot sits to its left and everything larger sits to its right. After that single sweep, the pivot is in its final sorted position — it will never move again — and you recurse on the two sides. No merge step, because once both sides are sorted, the array already is.

private static int partition(int[] a, int lo, int hi) {
    int r = lo + RNG.nextInt(hi - lo + 1);   // random pivot defeats sorted input
    swap(a, r, hi);
    int pivot = a[hi];
    int i = lo;                              // invariant: a[lo..i-1] are all < pivot
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            swap(a, i, j);
            i++;
        }
    }
    swap(a, i, hi);                          // drop the pivot into its final slot
    return i;
}

The rule: partition puts one element home and splits the rest into two independent problems. The loop keeps a boundary i: everything before i is known to be less than the pivot. Each time it finds another small element, it swaps that element down to the boundary and nudges i forward. One linear pass, and the pivot slots into position i. Because quicksort sorts in place, its only extra memory is the recursion stack — O(log n) when the splits are balanced, which is the whole appeal.

But look hard at that first line, RNG.nextInt(...). Why are we choosing the pivot at random? Because the obvious choice — “just use the first or last element” — has a catastrophic failure mode, and it’s the single most important thing to understand about quicksort.

Step 5 — the trap: a bad pivot, and the one-line fix

Here’s the bug. Suppose you always pick the last element as the pivot (drop the random line), and someone hands you an array that’s already sorted. The pivot is the largest element, so everything lands on its left and the right side is empty. You’ve split n elements into a side of n−1 and a side of 0 — you removed exactly one element and made no real progress.

Do that again and again and the recursion becomes a staircase n levels deep, each level scanning almost the whole array. The cost is n + (n−1) + … + 1 = O(n²) — quicksort has degraded into a slow insertion sort, and it blows the recursion stack too. The bitter irony: this happens on sorted or reverse-sorted input, which is exactly the data you’re most likely to be handed in real life. An interviewer who asks “what’s quicksort’s worst case?” is really asking “do you know your pivot can betray you?”

The fix is almost insultingly small. Make the pivot unpredictable, so no particular input order can force lopsided splits:

• Randomized pivot — pick the pivot at a random index (the one line above). Now no fixed input is adversarial; you’d have to be unlucky again and again, which happens with vanishing probability. Expected time is O(n log n).
• Median-of-three — look at the first, middle, and last elements and pivot on their median. Cheap, deterministic, and it makes already-sorted input — the common case — split perfectly down the middle.

Either way, the split is balanced enough that you get log n levels instead of n, and quicksort is back to its O(n log n) average. The worst case still technically exists, but you’ve made it astronomically unlikely rather than trivially triggerable.

There’s one more adversary worth naming: an array of all equal elements. The simple partition above puts every equal element on one side, so even a random pivot gives an n−1 / 0 split and O(n²) time. The industrial fix is three-way partitioning (Dijkstra’s “Dutch national flag”): split into < pivot, = pivot, and > pivot, so a run of duplicates lands in the middle and is never recursed on. That’s the version production libraries actually ship.

Heap sort, in one breath

There’s a third O(n log n) sort worth a sentence: heap sort. Build the array into a binary heap, then repeatedly pull the maximum off the top and drop it at the end. It sorts in place with O(1) extra space and guarantees O(n log n) even in the worst case — the best of merge and quick on paper. Its catch is that it’s not stable and its scattered memory access makes it slower in practice than a well-tuned quicksort. It’s the sort you reach for when you need a hard O(n log n) ceiling and can’t spare merge sort’s O(n) buffer.

Stability: the property you don’t notice until it bites

We keep touching stability, so let’s make it concrete. A sort is stable if elements that compare equal come out in the same order they went in. Sort records by one field, and a stable sort leaves records with equal fields in their original arrangement; an unstable sort may shuffle them.

It matters exactly when your elements carry more than the sort key — which is almost always in real systems. Sort a table of transactions by amount, and if two transactions tie, a stable sort keeps them in their original time order; an unstable one scrambles it. It’s also what makes the spreadsheet’s two-pass trick work: sort by the secondary key, then by the primary key, and a stable primary sort preserves the secondary order within each group. Chain stable sorts and you compose orderings for free.

Here’s the scorecard: merge sort and insertion sort are stable by nature (their tie-breaks favour the earlier element). Heap sort and the usual in-place quicksort are not — they swap elements across long distances, and those swaps don’t respect original order. If you need both quicksort’s speed and stability, you either pay for O(n) space (which is really merge sort) or sort on a composite key that encodes the original index to break ties deterministically.

The O(n log n) wall — and how counting sort walks around it

Now the deepest idea in the whole topic, and the one that separates memorising sorts from understanding them. Merge sort and heap sort both hit O(n log n) and no comparison sort ever does better in the worst case. That’s not for lack of trying — it’s a proven wall. Here’s the argument, and it’s beautiful.

Think of any sorting algorithm that works by comparing pairs of elements. Every run of it is a sequence of yes/no comparisons: “is a before b?” Each comparison has two outcomes, so the algorithm’s whole behaviour is a binary decision tree — each comparison a branch, each leaf a final arrangement it can output.

Now count. To sort n distinct elements, there are n! possible input orderings, and the algorithm must be able to produce a different sequence of moves for each one — because each ordering needs a different set of swaps to fix. So the decision tree needs at least n! leaves. And a binary tree with n! leaves must have height at least log₂(n!). The height is the number of comparisons in the worst case, so:

That approximation is Stirling’s: log₂(n!) grows like n log₂ n. So every comparison-based sort — no matter how clever — needs at least about n log n comparisons on its worst input. Merge sort and heap sort reach that floor exactly; they are, in this precise sense, optimal. There is no O(n) comparison sort hiding out there waiting to be discovered.

So how do you escape it? Stop comparing. Counting sort takes small-integer keys and, instead of comparing them, uses each value as an index: count how many times each value appears, then walk the counts to lay the output down in order — O(n + k) for keys in range k, no comparisons at all. Radix sort extends that to bigger keys by counting-sorting one digit at a time, from least significant to most, O(n · d) for d digits — and it leans on a stable inner sort so earlier digit passes survive later ones. These beat n log n because they exploit the structure of the keys (they’re bounded integers), which general comparison sorts aren’t allowed to assume. The trade-off is right there: they only work when your keys are small integers or fixed-width strings, and they cost memory proportional to the key range.

Choosing a sort: the trade-offs

There’s no universal best sort — there’s a best sort for your constraints. Here’s the whole field on one card.

And the same information as a decision aid — what each column means for when you reach for it:

The honest summary: quicksort is the default in-memory sort because its average speed and O(log n) space beat everything, and randomization tames its worst case. Merge sort wins when you need stability or a hard guarantee — which is why language libraries sort objects with a merge-sort variant (Timsort) and sort primitives with a quicksort variant (dual-pivot). They picked one of each, for exactly these trade-offs.

The complete implementation

Everything above, assembled — insertion for the small/near-sorted case, merge sort for stability, and a randomized quicksort that survives adversarial input:

package dev.fiveyear.sorting;
 
import java.util.Random;
 
public final class Sorts {
 
    private Sorts() {}
 
    private static final Random RNG = new Random();
 
    /** Insertion sort: O(n^2) worst, O(n) on nearly-sorted, stable. */
    public static void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {   // '>' keeps equals in place → stable
                a[j + 1] = a[j];             // shift the bigger element right
                j--;
            }
            a[j + 1] = key;                  // drop key into the gap
        }
    }
 
    /** Merge sort: O(n log n) always, stable, needs an O(n) buffer. */
    public static void mergeSort(int[] a) {
        if (a.length < 2) {
            return;
        }
        int[] buf = new int[a.length];
        mergeSort(a, buf, 0, a.length - 1);
    }
 
    private static void mergeSort(int[] a, int[] buf, int lo, int hi) {
        if (lo >= hi) {
            return;                          // length-1 run is already sorted
        }
        int mid = lo + (hi - lo) / 2;        // overflow-safe midpoint
        mergeSort(a, buf, lo, mid);
        mergeSort(a, buf, mid + 1, hi);
        merge(a, buf, lo, mid, hi);
    }
 
    private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) {
            if (a[j] < a[i]) {               // strict '<': left wins ties → stable
                buf[k++] = a[j++];
            } else {
                buf[k++] = a[i++];
            }
        }
        while (i <= mid) {
            buf[k++] = a[i++];
        }
        while (j <= hi) {
            buf[k++] = a[j++];
        }
        System.arraycopy(buf, lo, a, lo, hi - lo + 1);
    }
 
    /** Quicksort: O(n log n) average, in-place, randomized pivot. */
    public static void quickSort(int[] a) {
        quickSort(a, 0, a.length - 1);
    }
 
    private static void quickSort(int[] a, int lo, int hi) {
        while (lo < hi) {
            int p = partition(a, lo, hi);
            if (p - lo < hi - p) {           // recurse into the SMALLER side...
                quickSort(a, lo, p - 1);
                lo = p + 1;                  // ...loop on the larger → O(log n) stack
            } else {
                quickSort(a, p + 1, hi);
                hi = p - 1;
            }
        }
    }
 
    private static int partition(int[] a, int lo, int hi) {
        int r = lo + RNG.nextInt(hi - lo + 1);   // random pivot defeats sorted input
        swap(a, r, hi);
        int pivot = a[hi];
        int i = lo;                              // a[lo..i-1] are all < pivot
        for (int j = lo; j < hi; j++) {
            if (a[j] < pivot) {
                swap(a, i, j);
                i++;
            }
        }
        swap(a, i, hi);                          // pivot into its final slot
        return i;
    }
 
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

And here it is producing exactly the outputs the comments claim — including the adversarial cases that break a naive quicksort:

int[] a = {5, 2, 9, 1, 5, 6};
Sorts.insertionSort(a);            // [1, 2, 5, 5, 6, 9]
 
int[] b = {5, 2, 9, 1, 5, 6};
Sorts.mergeSort(b);                // [1, 2, 5, 5, 6, 9]  — stable: the two 5s keep order
 
int[] c = {5, 2, 9, 1, 5, 6};
Sorts.quickSort(c);                // [1, 2, 5, 5, 6, 9]
 
int[] sorted = {1, 2, 3, 4, 5};
Sorts.quickSort(sorted);           // [1, 2, 3, 4, 5]  — still O(n log n), the random pivot saves it
 
int[] reversed = {9, 7, 5, 3, 1};
Sorts.quickSort(reversed);         // [1, 3, 5, 7, 9]  — the other classic O(n^2) trap, defused
 
Sorts.mergeSort(new int[] {});     // []               — empty is a no-op

Every sort here was checked the honest way: fuzzed against the standard library’s result on hundreds of random arrays and on the four shapes that break careless code — already-sorted, reverse-sorted, all-equal, and organ-pipe — at sizes up to a few thousand. If the randomized pivot weren’t there, the sorted and reversed cases would either crawl or overflow the stack.

The interview corner

Sorting is the most likely warm-up you’ll get, and the trap is treating it as trivia. What they’re really testing is whether you understand trade-offs and worst cases. Here’s how to walk in ready.

Ask these before you write a line:

• “What am I sorting — primitives or objects with other fields, and do I need the sort to be stable?” Stability decides merge vs quick immediately. If ties carry meaning (secondary order, original position), you need a stable sort or a composite key.
• “How big is the data, and does it fit in memory?” A few dozen elements? Insertion sort, and don’t apologise. Millions in RAM? Quicksort. Bigger than RAM? You’re in external merge sort territory — sort chunks, then merge them off disk.
• “What do I know about the keys and the existing order?” Small-integer keys open the door to counting/radix and an O(n) sort. Nearly-sorted data makes insertion sort shine. The input’s shape changes the right answer.

The follow-up ladder — where a strong candidate keeps climbing:

1. “Make quicksort safe on sorted input.” Randomize the pivot or take median-of-three; add three-way partitioning for duplicate-heavy data. Recurse into the smaller side and loop on the larger to cap stack depth at O(log n).
2. “Sort objects by two fields — say, by age, then by name within each age.” Sort by the secondary key first, then a stable sort by the primary — or sort once with a comparator that compares age, then breaks ties on name. Both give the composite order; the stable-twice trick is the one that surprises people.
3. “Sort ten billion records that don’t fit in memory.” External merge sort: read memory-sized chunks, sort each in RAM, write them out, then k-way merge the sorted runs with a min-heap picking the smallest current head. Merge’s two-finger idea, scaled to k fingers on disk.
4. “Find the k-th smallest without fully sorting.” Quickselect — quicksort’s partition, but recurse into only the side that contains rank k. Average O(n), because you throw away half the work each step instead of sorting both halves.
5. “Beat O(n log n).” Only by not comparing: counting or radix sort on bounded-integer keys, O(n + k) or O(n · d). Name the comparison lower bound so they know you understand why that’s the only door out.

Three mistakes that fail the round:

• Claiming quicksort is O(n log n) worst case. It’s O(n log n) average and O(n²) worst — on sorted input with a fixed pivot. Saying “worst case n log n” tells the interviewer you’ve memorised a table without understanding the pivot.
• Forgetting merge sort’s O(n) space. “Merge sort is strictly better than quicksort” is wrong the moment memory is tight — quicksort sorts in place; merge sort needs a full second array. The space column is half the decision.
• Ignoring stability. Reaching for an unstable sort when the problem sorts objects with meaningful ties silently corrupts the secondary order. Always ask whether stability matters before picking the algorithm.

Where to go from here

You now own the core: a big sort is small local moves, scheduled well. Insertion grows a sorted prefix; merge sort splits and zips sorted runs; quicksort partitions around a pivot and lets a random choice defend it; and no comparison sort escapes the O(n log n) wall. Three natural next stops:

• Quickselect and order statistics — partition once, recurse into one side, and find the median (or any rank) in average O(n). It’s quicksort with 90% of the work deleted.
• Timsort and introsort — the hybrids your standard library actually runs: insertion sort for small runs, merge or quicksort for the rest, with a fallback to heap sort so the worst case can never bite. Real sorting is three algorithms in a trench coat.
• Sorting as a subroutine — once data is ordered, binary search, two-pointer scans, sliding windows, and interval-merging all fall out cheaply. Sorting is rarely the goal; it’s the setup that makes the next step easy.

Next time your hands tidy a dealt hand without being asked, you’ll know they’re running insertion sort — and that if the deck were a million cards, you’d want to split it, sort the halves, and merge.