The Merge Sort Algorithm

Quicksort reaches O(n log n) by partitioning around a pivot chosen from the data itself, which is what makes its worst case depend on input order. Merge sort gets the same complexity a different way, with a guarantee quicksort cannot make: it is O(n log n) every time, regardless of how the input is arranged — at the cost of needing a second array to work in.

The idea

A list of one element is already sorted. Two sorted lists can be combined into one larger sorted list by repeatedly taking whichever front element is smaller — that combining step is called a merge, and it only needs one pass through both lists, so merging two runs of length m takes O(m) work in total, not O(m log m).

Top-down merge sort applies this recursively: split the list in half, sort each half (recursively), then merge the two sorted halves. The sample below builds the same result bottom-up instead, which turns out to skip the recursion entirely: start by treating every single element as already "sorted" (a run of length 1), then repeatedly merge neighboring runs into runs twice the size — length 1 into length 2, length 2 into length 4, and so on — until one run covers the whole array. Doubling the run length each pass is exactly why there are only log₂ n passes.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int temp[N];

int width = 1; // size of each run being merged this pass
int lo, mid, hi;
int p, q, k;    // left run pointer, right run pointer, write pointer
bool merging = false;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }

    lo = 0;
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (!merging) {
            if (width >= N) {
                done = true;
            } else if (lo >= N) {
                width *= 2;
                lo = 0;
                if (width >= N) done = true;
            } else {
                mid = lo + width;
                if (mid > N) mid = N;
                hi = lo + 2 * width;
                if (hi > N) hi = N;

                if (mid >= hi) {
                    lo += 2 * width; // right run empty, nothing to merge here
                } else {
                    p = lo;
                    q = mid;
                    k = lo;
                    merging = true;
                }
            }
        } else {
            if (p < mid && (q >= hi || values[p] <= values[q])) {
                temp[k] = values[p];
                p++;
            } else {
                temp[k] = values[q];
                q++;
            }
            k++;

            if (k >= hi) {
                for (int n = lo; n < hi; n++) {
                    values[n] = temp[n];
                }
                lo += 2 * width;
                merging = false;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        int v;
        if (done) {
            PlotColor(70, 170, 90);   // fully sorted
            v = values[idx];
        } else if (merging && idx >= lo && idx < hi) {
            if (idx < k) {
                PlotColor(70, 170, 90);   // already merged this pass
                v = temp[idx];
            } else if (idx == p || idx == q) {
                PlotColor(220, 60, 60);   // heads currently being compared
                v = values[idx];
            } else {
                PlotColor(30, 100, 200);  // waiting in its run
                v = values[idx];
            }
        } else {
            PlotColor(30, 100, 200);      // not part of the active merge
            v = values[idx];
        }

        int height = v * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

width is the current run length; one full pass merges every adjacent pair of width-sized runs, then width doubles for the next pass. Inside a merge, p and q are the next-unmerged element of the left and right run, k is the write position in the scratch array temp, and each step just compares values[p] against values[q] and appends the smaller one. Once a run pair is fully merged, it gets copied from temp back into values in one block, and lo advances to the next pair.

Because a merge only ever reads from the original array and writes into temp, the visualization can show a run growing correctly-merged in place before it's copied back — that's what the growing green segment inside the active window is:

• blue — not part of the merge currently in progress
• red — the two run-heads currently being compared
• green — merged into temp already this pass (all bars turn green at once, briefly, once the whole array is one sorted run)

Walking through an example

Merging the two already-sorted runs [1, 4] and [2, 8]:

Result: [1, 2, 4, 8]. Each of the four elements gets examined exactly once — no rescanning — which is what keeps a merge at O(m) for two runs of combined length m, and the whole pass at O(n) for all runs of a given width combined.

Why the extra array is worth it

Merge sort's O(n log n) bound holds unconditionally, unlike quicksort's, because merging never depends on how the data happens to be arranged — only on how many elements there are. That predictability is valuable enough that merge sort (or a hybrid of it) is the default sort for data where worst-case behavior matters, or where stability is required — equal elements keep their relative order, since the merge step always prefers the left run on ties.

The cost is the temp array: merge sort needs O(n) extra memory, where quicksort and the simple sorts need none. It also tends to move more data around in practice than quicksort's in-place partitioning, which is the main reason quicksort is usually faster on typical inputs even though both are O(n log n) on average. Where merge sort wins outright is external sorting — sorting data too large to fit in memory — since merging sorted chunks read sequentially from disk plays to its strengths far better than quicksort's random-access partitioning would.

Conclusion

Across this series, the same underlying idea — reduce sorting to comparisons and rearrangements — produces very different algorithms depending on how the work is structured: rescanning neighbors, growing a sorted prefix, or dividing the problem and combining the results. Merge sort's contribution is a guarantee: no matter what the input looks like, merging sorted runs costs exactly what it costs, and nothing more.