Merge sort

Why it exists

Merge sort is the standard answer to "sort with a guaranteed $n \log n$ running time and keep equal keys in order". It never degenerates, it is stable, it reads its input sequentially (which is why it is the basis of sorting data on disk and of sorting linked lists), and it is the cleanest example of divide and conquer whose recurrence is $T(n) = 2T(n/2) + \Theta(n)$. Its price is $\Theta(n)$ extra memory when sorting an array.

Prerequisites

You need the divide and conquer pattern and its recurrence (divide and conquer).

Precise definitions

Run. A sorted contiguous piece of an array (or a sorted list).

Merge. Given two sorted runs, produce one sorted run containing all their keys. Keep a pointer at the front of each run, repeatedly compare the two front keys, and move the smaller to the output; when one run is used up, copy the rest of the other.

Merge sort (top-down). To sort $a_{lo}, \ldots, a_{hi-1}$: if there are fewer than two keys, stop. Otherwise sort the left half, sort the right half, and merge the two runs.

Bottom-up merge sort. Merge runs of length $1$ into runs of length $2$, these into runs of length $4$, and so on, without recursion.

Cost measure. The number of comparisons of two keys (the data movement is $\Theta(n)$ per level, so it has the same order).

How it works

The merge and its invariant. Let $i$ and $j$ be the fronts of the left and right run and $k$ the next free slot of the temporary array. The invariant is: $\text{tmp}[lo..k-1]$ holds, in sorted order, the $k - lo$ smallest keys of the two runs, and every key still waiting is at least as large as every key in it. Each step moves the smaller front key, so it keeps the invariant. If the two front keys are equal the left one is taken; this single rule makes the sort stable, because equal keys of the left run come from earlier positions.

The code and a real run. The code below is what the animation runs, on $6, 3, 8, 1, 7, 2, 5, 4$. Watch the faded cells: only the range being merged is active, and the lower row is the temporary array.

Counting comparisons. Merging runs of sizes $p$ and $q$ takes at least $\min(p, q)$ comparisons (one run is used up first, then the rest of the other is copied without comparisons) and at most $p + q - 1$ (the last key is never compared against anything). Moving the keys costs $p + q$ copies. Consequences for $n = 2^k$ keys, with $k$ levels of merging:

• Worst case: every merge takes $p + q - 1$ comparisons, so the total is $n$ per level minus one per merge: $\sum_{\text{levels}} (n - \text{number of merges}) = kn - (n - 1) = n \log_2 n - n + 1$. For any $n$ the worst case is $W(n) = n \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1$.
• Best case (already sorted, or reversed): in each merge one whole run is smaller than the other, so only $\min(p, q) = n'/2$ comparisons are made per merge, $n/2$ per level: $\frac{n}{2} \log_2 n$.

The C program below runs merge sort on a sorted, a reversed, a random and a specially built worst-case input (the even-position keys go to the left half and the odd-position keys to the right half, recursively, so that every merge interleaves) and counts comparisons.

#include <stdio.h>
 
static long cmps;
 
static void merge(int a[], int tmp[], int lo, int mid, int hi) {
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        cmps++;
        if (a[j] < a[i]) tmp[k++] = a[j++];
        else tmp[k++] = a[i++];
    }
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi) tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
}
 
static void merge_sort(int a[], int tmp[], int lo, int hi) {
    if (hi - lo < 2) return;
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, tmp, lo, mid);
    merge_sort(a, tmp, mid, hi);
    merge(a, tmp, lo, mid, hi);
}
 
/* an input on which every merge needs the most comparisons: send the even positions of the sorted order to the left half
   and the odd positions to the right half, recursively, so that the two runs of every merge interleave */
static void worst_case(int a[], int tmp[], int n) {
    if (n < 2) return;
    int h = n / 2;
    for (int i = 0; i < n; i++) tmp[i] = a[i];
    for (int i = 0; i < h; i++) a[i] = tmp[2 * i];
    for (int i = 0; i < n - h; i++) a[h + i] = tmp[2 * i + 1];
    worst_case(a, tmp, h);
    worst_case(a + h, tmp, n - h);
}
 
static long run(int a[], int n) {
    static int tmp[1024];
    cmps = 0;
    merge_sort(a, tmp, 0, n);
    for (int i = 1; i < n; i++) if (a[i - 1] > a[i]) return -1;   /* not sorted: report failure */
    return cmps;
}
 
int main(void) {
    static int a[1024], t[1024];
    int ns[] = {8, 16, 64, 1024};
    unsigned s = 2024;
    printf("%5s %8s %9s %8s %8s\n", "n", "sorted", "reversed", "worst", "random");
    for (int q = 0; q < 4; q++) {
        int n = ns[q];
        for (int i = 0; i < n; i++) a[i] = i;
        long c1 = run(a, n);
        for (int i = 0; i < n; i++) a[i] = n - i;
        long c2 = run(a, n);
        for (int i = 0; i < n; i++) a[i] = i;
        worst_case(a, t, n);
        long c3 = run(a, n);
        for (int i = 0; i < n; i++) { s = s * 1103515245u + 12345u; a[i] = (int)((s >> 8) % 100000); }
        long c4 = run(a, n);
        printf("%5d %8ld %9ld %8ld %8ld\n", n, c1, c2, c3, c4);
    }
    return 0;
}

    n   sorted  reversed    worst   random
    8       12        12       17       15
   16       32        32       49       46
   64      192       192      321      307
 1024     5120      5120     9217     8928

Recurrence and time. Dividing costs $\Theta(1)$, merging costs $\Theta(n)$: $T(n) = 2T(n/2) + \Theta(n),$ and by the Master theorem (case 2) $T(n) = \Theta(n \log n)$, in the best, average and worst case alike: merge sort does not get faster on sorted input beyond a constant factor (the best case is still $\frac{n}{2}\log_2 n$ comparisons).

Space. The array version needs a temporary array of $n$ keys ($\Theta(n)$ extra space, not in place) and a recursion stack of depth $\lceil \log_2 n \rceil$. A merge of two runs in the array itself, without the temporary array, exists but is complicated and slower. The linked-list version needs no temporary array at all: merging relinks the nodes, giving $O(1)$ extra nodes plus $O(\log n)$ stack (or $O(1)$ for the bottom-up version), and it stays stable. This is why merge sort is the method of choice for linked lists.

Stability. Stable, by the tie rule above. (An implementation that takes the right key on a tie is correct but not stable.)

Merging many runs. To merge $k$ sorted lists with $n$ keys in total, keep the $k$ front keys in a min-heap (priority queue): each of the $n$ output keys costs one extraction and one insertion, $O(\log k)$, so the time is $O(n \log k)$. External sorting uses this: sort pieces that fit in memory, then merge them in few passes.

Inversions and other uses. Counting how many times a key from the right run is taken before keys of the left run counts the inversions of the input in $\Theta(n \log n)$ (divide and conquer applications).

Worked examples

Cheat box

Traps and GATE patterns

Connections

Merge sort is the standard example of divide and conquer; its recurrence is solved in solving recurrences. It is compared with quicksort and heap sort in stability and comparison of sorts, and its comparison count is close to the information-theoretic minimum of the lower bound. Counting inversions during the merge is in divide and conquer applications.

PYQs

Consider an array A = [10, 7, 8, 19, 41,35, 25, 31].
Suppose the merge sort algorithm is executed on
array A to sort it in increasing order. The merge
sort algorithm will carry out a total of 7 merge
operations.
A merge operation on sorted left array L and
sorted right array R is said to be void if the output
of the merge operation is the elements of array L
followed by the elements of array R.
The number of void merge operations among
these 7 merge operations is
. (answer in
integer)

The worst-case running time of Insertion sort,
Merge sort and Quick sort, respectively, are:

A list of n strings, each of length n, is sorted
into lexicographic order using the merge-sort
algorithm. The worst case running time of this
computation is

The average case and worst case complexities
for Merge sort algorithm are

Consider the following C-function in which a[n] and
b[m] are two sorted integer arrays and c[n+m] be
another integer array.

void xyz(int a[], int b[], int c[])

{

int i, j, k;

i = j = k = 0;

while ((i < n) && (j < m))
        if (a[i] < b[j])

c[k++] = a[i++];
        else

c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the
termination of the while loop?

(i) j<m,  k=n+j-1,  and a[n-1]<b[j] if i=n

(ii) i<n,  k=m+i-1,  and b[m-1]≤a[i] if j=m

Self-check

Revision card

References