Merge Sort in C, C++, Java, Python and C#: Top-Down, Bottom-Up and Linked Lists

Merge sort is the one algorithm in this series that is both stable and O(n log n) on every input. Its worst case is its average case. The costs sit elsewhere, and they are easier to measure than to guess. A common one-line optimization cut comparisons on sorted input from 64,608 to 9,999, and added 14% on reversed input. Allocating a buffer inside every merge made 999,999 calls to malloc() for a million elements and cost 11–14% of the running time, less than its reputation suggests.

This guide traces merge sort on a small array, then gives top-down, bottom-up and linked-list implementations in C, a generic C++ version, and versions in Java, Python and C#. It measures the comparisons against the worst-case bound and uses merge sort to count inversions. It closes with four mistakes, two of which behave differently depending on the optimization level. Every program was compiled and run for this article on Ubuntu 24.04: C with GCC 13.3 and Clang 18.1.3 (-std=c11 and -std=c17), C++ with g++ 13.3 and clang++ 18.1.3 (-std=c++17 and -std=c++20), all with -Wall -Wextra -pedantic and no warnings; Java on OpenJDK 21, Python 3.11 (also checked with ruff and mypy --strict), and C# on .NET 10 with analyzer warnings as errors. All five sort the same array and print the same result. The C and C++ code is in GitHub repositories whose builds run the tests on each change.

What Is Merge Sort?

Merge sort is a divide-and-conquer sorting algorithm that splits an array into two halves, sorts each half recursively, and merges the two sorted halves into one sorted run. The merge step does the work: it repeatedly takes the smaller of the two front elements. Merge sort makes O(n log n) comparisons on every input, is stable, and needs O(n) extra memory for arrays.

The merge is where stability comes from. When the two front elements are equal, taking the one from the left half keeps equal keys in their original order. That property is why merge sort, rather than quicksort, is the basis of the standard stable sorts: libstdc++’s std::stable_sort is a merge sort with a temporary buffer, and Java’s object sort and Python’s sorted() both use Timsort, a merge sort that detects runs already in order.

How Merge Sort Works

1. Split the range [lo, hi) at mid = lo + (hi − lo) / 2.
2. Sort [lo, mid) and [mid, hi) recursively. A range of 0 or 1 element is already sorted.
3. Merge the two sorted halves: compare the front elements, copy the smaller one to a buffer, and advance. On a tie, take from the left.
4. Copy the merged run back into [lo, hi).

The bottom-up version skips step 1’s recursion: it merges runs of width 1 into runs of width 2, then 4, and so on, until one run covers the array.

Worked Example

Sorting 29 10 14 37 13 5 41 22, one level of merges per line, as printed by the trace program in the repository (which counts every comparison and has no shortcut for halves already in order):

Output:

runs of 2:  [10 29] 1 cmp  [14 37] 1 cmp  [5 13] 1 cmp  [22 41] 1 cmp
runs of 4:  [10 14 29 37] 3 cmp  [5 13 22 41] 2 cmp
runs of 8:  [5 10 13 14 22 29 37 41] 7 cmp
total comparisons: 16

Each level touches all eight elements once, and there are log₂ 8 = 3 levels. A merge of two runs of total length m makes at most m − 1 comparisons, and at least the length of the shorter run, which happens when one run is exhausted before the other is touched. Merging [10 14 29 37] with [5 13 22 41] needed 7 comparisons, the maximum for 8 elements, because the values interleave all the way to the end. For any 8-element input this merge makes between 12 and 17 comparisons in total.

Merge Sort in C

The header declares the two array sorts, a linked-list sort and an inversion counter, all of which are in the same source file:

/* merge_sort.h - merge sort for int arrays and linked lists, and
 * inversion counting */
#ifndef MERGE_SORT_H
#define MERGE_SORT_H

#include <stddef.h>

int merge_sort(int a[], size_t n);            /* top-down; -1 if malloc fails */
int merge_sort_bottom_up(int a[], size_t n);  /* iterative; -1 if malloc fails */

struct node {
    int value;
    struct node *next;
};
struct node *list_merge_sort(struct node *head);   /* no buffer; O(log n) stack */

/* Number of pairs i < j with a[i] > a[j]. Sorts a as a side effect.
 * Returns -1 (as unsigned long long: ULLONG_MAX) if malloc fails. */
unsigned long long count_inversions(int a[], size_t n);

#endif

/* merge_sort.c - merge sort in C11.
 * SORT_LESS(x, y) means "x sorts before y". Test programs redefine it
 * before including this file, to count comparisons. MERGE_SKIP_SORTED
 * (default 1) skips a merge when the two halves are already in order. */
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"

#ifndef SORT_LESS
#define SORT_LESS(x, y) ((x) < (y))
#endif
#ifndef MERGE_SKIP_SORTED
#define MERGE_SKIP_SORTED 1
#endif

/* Merges the sorted runs a[lo..mid) and a[mid..hi) through buf. On a tie
 * the left element goes first, which is what makes the sort stable. */
static void merge(int a[], int buf[], size_t lo, size_t mid, size_t hi)
{
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        buf[k++] = SORT_LESS(a[j], a[i]) ? a[j++] : a[i++];
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hi - lo) * sizeof a[0]);
}

/* Sorts the half-open range a[lo..hi). */
static void merge_sort_rec(int a[], int buf[], size_t lo, size_t hi)
{
    if (hi - lo < 2)                         /* 0 or 1 element: sorted */
        return;
    size_t mid = lo + (hi - lo) / 2;         /* cannot overflow */
    merge_sort_rec(a, buf, lo, mid);
    merge_sort_rec(a, buf, mid, hi);
    if (MERGE_SKIP_SORTED && !SORT_LESS(a[mid], a[mid - 1]))
        return;                              /* halves already in order */
    merge(a, buf, lo, mid, hi);
}

int merge_sort(int a[], size_t n)
{
    if (n < 2)
        return 0;
    int *buf = malloc(n * sizeof *buf);      /* one buffer for every merge */
    if (buf == NULL)
        return -1;
    merge_sort_rec(a, buf, 0, n);
    free(buf);
    return 0;
}

/* Bottom-up: merge runs of width 1, 2, 4, ... No recursion. */
int merge_sort_bottom_up(int a[], size_t n)
{
    if (n < 2)
        return 0;
    int *buf = malloc(n * sizeof *buf);
    if (buf == NULL)
        return -1;
    for (size_t width = 1; width < n; width *= 2)
        for (size_t lo = 0; lo < n - width; lo += 2 * width) {
            size_t mid = lo + width;
            size_t hi = (n - mid > width) ? mid + width : n;
            merge(a, buf, lo, mid, hi);
        }
    free(buf);
    return 0;
}

/* Linked list: split with slow/fast pointers, merge by relinking nodes. */
static struct node *list_merge(struct node *x, struct node *y)
{
    struct node head = { 0, NULL }, *tail = &head;
    while (x != NULL && y != NULL) {
        if (SORT_LESS(y->value, x->value)) { tail->next = y; y = y->next; }
        else                               { tail->next = x; x = x->next; }
        tail = tail->next;
    }
    tail->next = (x != NULL) ? x : y;
    return head.next;
}

struct node *list_merge_sort(struct node *head)
{
    if (head == NULL || head->next == NULL)
        return head;
    struct node *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct node *second = slow->next;        /* cut the list in two */
    slow->next = NULL;
    return list_merge(list_merge_sort(head), list_merge_sort(second));
}

/* Inversion counting: when an element is taken from the right run, it is
 * smaller than every element still waiting in the left run. */
static unsigned long long count_rec(int a[], int buf[], size_t lo, size_t hi)
{
    if (hi - lo < 2)
        return 0;
    size_t mid = lo + (hi - lo) / 2;
    unsigned long long inv = count_rec(a, buf, lo, mid) + count_rec(a, buf, mid, hi);
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (SORT_LESS(a[j], a[i])) {
            inv += mid - i;                  /* a[j] < a[i..mid) */
            buf[k++] = a[j++];
        } else {
            buf[k++] = a[i++];
        }
    }
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hi - lo) * sizeof a[0]);
    return inv;
}

unsigned long long count_inversions(int a[], size_t n)
{
    if (n < 2)
        return 0;
    int *buf = malloc(n * sizeof *buf);
    if (buf == NULL)
        return (unsigned long long)-1;
    unsigned long long inv = count_rec(a, buf, 0, n);
    free(buf);
    return inv;
}

A program that calls all four:

/* merge_example.c - arrays, a linked list, and inversion counting */
#include <stdio.h>
#include <limits.h>
#include "merge_sort.h"

static void print_array(const char *label, const int a[], size_t n)
{
    printf("%-11s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d", a[i]);
    printf("\n");
}

int main(void)
{
    int a[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int b[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int c[] = { 29, 10, 14, 37, 13, 5, 41, 22 };
    int edge[] = { 0, INT_MAX, -1, INT_MIN, 0 };
    size_t n = sizeof a / sizeof a[0];

    print_array("before:", a, n);
    if (merge_sort(a, n) != 0 || merge_sort_bottom_up(b, n) != 0) {
        fputs("out of memory\n", stderr);
        return 1;
    }
    print_array("top-down:", a, n);
    print_array("bottom-up:", b, n);

    struct node nodes[8], *head = NULL;      /* build a list 29 -> 10 -> ... */
    for (size_t i = n; i-- > 0; ) {
        nodes[i].value = c[i];
        nodes[i].next = head;
        head = &nodes[i];
    }
    head = list_merge_sort(head);
    printf("%-11s", "list:");
    for (struct node *p = head; p != NULL; p = p->next)
        printf(" %d", p->value);
    printf("\n");

    printf("inversions: %llu\n", count_inversions(c, n));
    if (merge_sort(edge, 5) != 0)
        return 1;
    print_array("limits:", edge, 5);
    return 0;
}

Output:

before:     29 10 14 37 13 5 41 22
top-down:   5 10 13 14 22 29 37 41
bottom-up:  5 10 13 14 22 29 37 41
list:       5 10 13 14 22 29 37 41
inversions: 13
limits:     -2147483648 -1 0 0 2147483647

The choices in the C code:

• One buffer, allocated once. merge_sort() allocates n integers before recursing and every merge reuses them. It returns -1 if malloc() fails rather than returning with the array unsorted and no indication.
• Half-open ranges. [lo, hi) makes the split [lo, mid) + [mid, hi) exact, and the base case is hi - lo < 2.
• mid = lo + (hi - lo) / 2. With size_t indices, lo + hi cannot go negative but can still wrap on a huge array; the difference form cannot. The mistakes section shows what (lo + hi) / 2 does with int indices.
• Ties go left. SORT_LESS(a[j], a[i]) takes from the right only when that element is strictly smaller.
• The list version needs no buffer. It relinks nodes instead of copying values. It still recurses, so it uses O(log n) stack.

Comparisons, Measured

The counting program sorts 10,000 values in five arrangements (the same five, generated the same way, as in the insertion sort article) and counts comparisons for the top-down and bottom-up versions. It also counts inversions with count_inversions() and checks the result against a brute-force O(n²) count. The repository builds the program twice. First with the check that skips a merge when a[mid − 1] <= a[mid]:

Output:

MERGE_SKIP_SORTED = 1, n = 10000
input                 top-down   bottom-up    inversions   brute force
sorted                    9999       71712             0             0
reversed                 79007       64632      49994942      49994942
random                  127152      123669      25183572      25183572
local (within 8)         65772       76399         17736         17736
100 far swaps            79514      100845        810213        810213

and then without it:

Output:

MERGE_SKIP_SORTED = 0, n = 10000
input                 top-down   bottom-up    inversions   brute force
sorted                   64608       71712             0             0
reversed                 69034       64632      49994942      49994942
random                  120346      123669      25183572      25183572
local (within 8)         72573       76399         17736         17736
100 far swaps            94861      100845        810213        810213

Four things stand out:

• The worst-case bound holds. For top-down merge sort the maximum is n⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1, which is 10,000 × 14 − 16,384 + 1 = 123,617 comparisons for n = 10,000. Without the skip check, the random input needed 120,346, within 3% of that bound; merge sort’s best and worst differ by far less than insertion sort’s 9,999 and 49,995,000.
• The skip check is a trade. When two halves are already in order, one comparison replaces a whole merge. That took sorted input from 64,608 comparisons to 9,999, and saved 9% on the locally shuffled input and 16% on the input with 100 far swaps. On random input the check almost never succeeds, so it added 6,806 comparisons (5.7%); on reversed input it succeeds only where equal values meet, and added 9,973 (14%). Timsort, used by Java and Python, detects existing order in a more general way, finding whole runs rather than checking one pair per merge.
• Bottom-up made a different number of comparisons, because for n = 10,000, which is not a power of two, its runs are split differently: it doubles fixed widths from the left, leaving a short final run at each level. It made 123,669 on random input, just above the top-down bound, which does not apply to it.
• The inversion counts match the brute-force counts exactly on all five inputs, and match the inversion counts measured independently in the insertion sort article: 25,183,572 for the random input.

Counting inversions with merge sort

An inversion is a pair i < j with a[i] > a[j]. During a merge, when an element is taken from the right run, it is smaller than every element still waiting in the left run, and each of those forms one inversion with it. So count_rec() adds mid − i at that moment, and the whole count takes O(n log n) instead of the O(n²) of checking every pair. On the 10,000-element inputs above, the brute-force loop made about 50 million comparisons per input; the merge-based count made no more than a merge sort does.

How This Was Measured

No CPU pinning or frequency-scaling control was used, and all timings come from this one virtual machine. The comparison counts above do not depend on it.

Timings: Top-Down, Bottom-Up and qsort()

One run of the timing program built with GCC:

Output:

ms, n = 1000000, median of 5     random     sorted
top-down merge sort                  105.7        4.4
bottom-up merge sort                 105.5       17.6
qsort() glibc                        154.9       34.9

Across three runs per compiler (milliseconds, n = 1,000,000):

The two versions ran at about the same speed on random input. On sorted input the top-down version finished in under 5 ms because of the skip check: it compares at each split and never merges. The bottom-up version has no such check and still copied every element at every level, although each merge was cheap. glibc’s qsort(), which is itself a merge sort (see the Use the Library section), took about 1.5 to 2 times as long as the hand-written version on random input; it calls the comparator through a function pointer on every comparison, which the hand-written version compiled with < inline does not. That explanation is an inference: no profiler was run.

Four Merge Sort Mistakes

1. (lo + hi) / 2 With int Indices

The midpoint of two int indices overflows once their sum passes INT_MAX, which happens for any array over about a billion elements. The arithmetic can be shown without the array:

/* midpoint_overflow.c - (lo + hi) / 2 with int indices near INT_MAX.
 * Needs no huge array: the arithmetic is computed before any access. */
#include <stdio.h>

static int mid_sum(int lo, int hi)  { return (lo + hi) / 2; }        /* overflows */
static int mid_diff(int lo, int hi) { return lo + (hi - lo) / 2; }   /* does not  */

int main(void)
{
    int lo = 1500000000, hi = 2000000000;    /* a range inside a 2-billion array */
    printf("(lo + hi) / 2      = %d\n", mid_sum(lo, hi));
    printf("lo + (hi - lo) / 2 = %d\n", mid_diff(lo, hi));
    return 0;
}

Output (GCC and Clang, -O2):

(lo + hi) / 2      = -397483648
lo + (hi - lo) / 2 = 1750000000

Signed overflow is undefined behavior in C; here it produced a negative index, which a real merge sort would pass to a[mid]. UndefinedBehaviorSanitizer names it:

midpoint_overflow.c:5:50: runtime error: signed integer overflow: 1500000000 + 2000000000 cannot be represented in type 'int'

This exact bug in binary search and merge sort code was the subject of Joshua Bloch’s 2006 post Nearly All Binary Searches and Mergesorts are Broken. Use lo + (hi - lo) / 2, and size_t for indices.

2. The Wrong Base Case for Half-Open Ranges

With half-open ranges [lo, hi), a one-element range has hi == lo + 1. The base case if (lo >= hi) return;, correct for closed ranges, does not stop it:

/* base_case.c - with half-open ranges [lo, hi), "stop when lo >= hi" never
 * stops on a one-element range: it splits [lo, lo+1) into [lo, lo) and
 * [lo, lo+1) forever. */
#include <stdio.h>
#include <stddef.h>

static void sort_range(int a[], size_t lo, size_t hi)
{
    if (lo >= hi)                            /* should be: hi - lo < 2 */
        return;
    size_t mid = lo + (hi - lo) / 2;
    sort_range(a, lo, mid);
    sort_range(a, mid, hi);
    /* no merge needed to show the bug: the calls above never return */
}

int main(void)
{
    int a[] = { 3, 1, 2 };
    sort_range(a, 0, 3);
    printf("%d %d %d\n", a[0], a[1], a[2]);
    return 0;
}

A one-element range [lo, lo + 1) splits into [lo, lo), which returns, and [lo, lo + 1) again, forever. What that looked like depended on the optimization level:

In Clang’s -O2 assembly the second recursive call, the one in tail position, has become a backward jump, so the repeated one-element range loops forever without using more stack. GCC restructured the function more heavily and I did not trace its code, but it showed the same behavior: no crash, no output. The same bug is a crash in a debug build and a hang in a release build. The fix is the base case in the C code above: if (hi - lo < 2) return;.

3. Taking From the Right on Ties

This program merges records by key twice: once taking from the right only when the right key is strictly smaller, and once when it is smaller or equal:

/* ties_right.c - taking from the right run on ties still sorts, but it
 * reverses the order of equal keys */
#include <stdio.h>
#include <string.h>
#include <stddef.h>

typedef struct { int key; char tag; } Item;

static void sort_items(Item a[], Item buf[], size_t lo, size_t hi, int ties_right)
{
    if (hi - lo < 2)
        return;
    size_t mid = lo + (hi - lo) / 2;
    sort_items(a, buf, lo, mid, ties_right);
    sort_items(a, buf, mid, hi, ties_right);
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        int take_right = ties_right ? a[j].key <= a[i].key    /* wrong */
                                    : a[j].key <  a[i].key;   /* right */
        buf[k++] = take_right ? a[j++] : a[i++];
    }
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hi - lo) * sizeof a[0]);
}

static void show(const char *label, const Item a[], size_t n)
{
    printf("%s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %d%c", a[i].key, a[i].tag);
    printf("\n");
}

int main(void)
{
    Item x[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} }, bx[5];
    Item y[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} }, by[5];
    show("input:           ", x, 5);
    sort_items(x, bx, 0, 5, 0);
    show("right only if <: ", x, 5);
    sort_items(y, by, 0, 5, 1);
    show("right if <=:     ", y, 5);
    return 0;
}

Output:

input:            2a 1b 2c 1d 2e
right only if <:  1b 1d 2a 2c 2e
right if <=:      1d 1b 2e 2c 2a

Both are sorted by key, so a sortedness test passes both. The second reversed both groups of equal keys, which removes the property most programs choose merge sort for.

4. Allocating Inside Every Merge

A common first version allocates the temporary array inside merge(). It works, and it calls malloc() once per merge: n − 1 times.

/* malloc_per_merge.c - allocating a temporary array inside every merge.
 * It sorts correctly; count the allocations and time it on 1,000,000 ints.
 * POSIX (clock_gettime). */
#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define N 1000000

static unsigned long long allocations;

static void merge_alloc(int a[], size_t lo, size_t mid, size_t hi)
{
    int *tmp = malloc((hi - lo) * sizeof *tmp);        /* one per merge */
    if (tmp == NULL) { fputs("out of memory\n", stderr); exit(1); }
    allocations++;
    size_t i = lo, j = mid, k = 0;
    while (i < mid && j < hi)
        tmp[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi)  tmp[k++] = a[j++];
    memcpy(a + lo, tmp, (hi - lo) * sizeof *tmp);
    free(tmp);
}

static void sort_alloc(int a[], size_t lo, size_t hi)
{
    if (hi - lo < 2)
        return;
    size_t mid = lo + (hi - lo) / 2;
    sort_alloc(a, lo, mid);
    sort_alloc(a, mid, hi);
    merge_alloc(a, lo, mid, hi);
}

static void merge_once(int a[], int buf[], size_t lo, size_t mid, size_t hi)
{
    size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
    while (i < mid) buf[k++] = a[i++];
    while (j < hi)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hi - lo) * sizeof *buf);
}

static void sort_once(int a[], int buf[], size_t lo, size_t hi)   /* same, one buffer */
{
    if (hi - lo < 2)
        return;
    size_t mid = lo + (hi - lo) / 2;
    sort_once(a, buf, lo, mid);
    sort_once(a, buf, mid, hi);
    merge_once(a, buf, lo, mid, hi);
}

static double now_ms(void)
{
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return (double)t.tv_sec * 1e3 + (double)t.tv_nsec / 1e6;
}

static int cmp_double(const void *pa, const void *pb)
{
    double a = *(const double *)pa, b = *(const double *)pb;
    return (a > b) - (a < b);
}

int main(void)
{
    int *in = malloc(N * sizeof *in), *a = malloc(N * sizeof *a), *b = malloc(N * sizeof *b);
    int *buf = malloc(N * sizeof *buf);
    if (!in || !a || !b || !buf) { fputs("out of memory\n", stderr); return 1; }
    unsigned long long xs = 88172645463325252ULL;
    for (size_t i = 0; i < N; i++) {
        xs ^= xs << 13; xs ^= xs >> 7; xs ^= xs << 17;
        in[i] = (int)(xs % 1000000000);
    }
    double ta[5], tb[5];
    for (int r = 0; r < 5; r++) {                 /* interleaved, median of 5 */
        memcpy(a, in, N * sizeof *a);
        memcpy(b, in, N * sizeof *b);
        allocations = 0;
        double t0 = now_ms();
        sort_alloc(a, 0, N);
        double t1 = now_ms();
        sort_once(b, buf, 0, N);
        double t2 = now_ms();
        ta[r] = t1 - t0;
        tb[r] = t2 - t1;
        if (memcmp(a, b, N * sizeof *a) != 0) { puts("results DIFFER"); return 1; }
    }
    qsort(ta, 5, sizeof ta[0], cmp_double);
    qsort(tb, 5, sizeof tb[0], cmp_double);
    printf("malloc per merge: %llu allocations, median %.1f ms\n", allocations, ta[2]);
    printf("one buffer:       1 allocation, median %.1f ms\n", tb[2]);
    printf("results identical\n");
    free(in); free(a); free(b); free(buf);
    return 0;
}

Output (GCC, one of three runs):

malloc per merge: 999999 allocations, median 121.0 ms
one buffer:       1 allocation, median 108.2 ms
results identical

Across three runs, one allocation per merge took 117–121 ms against 104–108 ms for one buffer with GCC, and 86–88 ms against 75–77 ms with Clang: about 11–14% slower. That is less than the call count suggests. The likeliest reason is that most merges are small and glibc’s allocator hands the same small blocks back quickly after each free(); that is an inference, not a measurement of the allocator. The first version of this experiment timed each method once instead of taking medians, and in one of its runs the malloc version came out faster. Single runs could not tell the two apart. The single buffer is still the right design: it also makes out-of-memory a single check at the start instead of a failure that can occur in the middle of a sort.

Merge Sort Time and Space Complexity

Merge Sort in C++, Java, Python and C#

C++

The C++ template sorts any random-access range with a comparator. Its buffer is a std::vector reserved once; clear() keeps the capacity, so later merges do not reallocate. Elements are moved, not copied, so it also sorts std::string and move-only types efficiently:

// merge_sort.hpp - generic top-down merge sort for C++17
#ifndef MERGE_SORT_HPP
#define MERGE_SORT_HPP

#include <functional>
#include <iterator>
#include <utility>
#include <vector>

namespace detail {

template <class RandomIt, class T, class Compare>
void merge_sort_rec(RandomIt first, RandomIt last, std::vector<T>& buf, Compare& comp)
{
    auto n = last - first;
    if (n < 2)
        return;
    RandomIt mid = first + n / 2;
    merge_sort_rec(first, mid, buf, comp);
    merge_sort_rec(mid, last, buf, comp);
    if (!comp(*mid, *std::prev(mid)))            // halves already in order
        return;

    buf.clear();                                 // capacity is kept: no reallocation
    RandomIt i = first, j = mid;
    while (i != mid && j != last)
        buf.push_back(comp(*j, *i) ? std::move(*j++) : std::move(*i++));  // ties: left first
    while (i != mid)
        buf.push_back(std::move(*i++));
    std::move(buf.begin(), buf.end(), first);    // the rest of [j, last) is already in place
}

}  // namespace detail

// Stable, O(n log n) comparisons on every input, O(n) extra memory.
// comp(a, b) means "a goes before b", as in std::sort.
template <class RandomIt, class Compare = std::less<>>
void merge_sort(RandomIt first, RandomIt last, Compare comp = {})
{
    using T = typename std::iterator_traits<RandomIt>::value_type;
    std::vector<T> buf;
    buf.reserve(static_cast<std::size_t>(last - first));   // one allocation
    detail::merge_sort_rec(first, last, buf, comp);
}

#endif

// merge_demo.cpp - the generic merge sort, and the standard library's
// merge-based sorts
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <string>
#include <vector>
#include "merge_sort.hpp"

template <class Range>
void print(const char* label, const Range& r)
{
    std::cout << label;
    for (const auto& x : r) std::cout << ' ' << x;
    std::cout << '\n';
}

struct Employee {
    std::string name;
    int dept;
};

int main()
{
    std::vector<int> v{29, 10, 14, 37, 13, 5, 41, 22};
    merge_sort(v.begin(), v.end());
    print("ascending: ", v);

    merge_sort(v.begin(), v.end(), std::greater<>{});
    print("descending:", v);

    std::vector<std::string> words{"pear", "fig", "apple", "kiwi", "date"};
    merge_sort(words.begin(), words.end());
    print("strings:   ", words);

    std::list<int> l{29, 10, 14, 37, 13, 5, 41, 22};
    l.sort();                                    // the list's own merge sort
    print("list.sort: ", l);

    std::vector<Employee> staff{
        {"Ava", 2}, {"Ben", 2}, {"Cleo", 1}, {"Dev", 3}, {"Eli", 1}, {"Fay", 2}};
    auto expected = staff;
    auto by_dept = [](const Employee& a, const Employee& b) { return a.dept < b.dept; };
    merge_sort(staff.begin(), staff.end(), by_dept);
    std::stable_sort(expected.begin(), expected.end(), by_dept);
    std::cout << "by dept:   ";
    for (const auto& e : staff) std::cout << ' ' << e.dept << ':' << e.name;
    bool same = std::equal(staff.begin(), staff.end(), expected.begin(),
                           [](const Employee& a, const Employee& b) { return a.name == b.name; });
    std::cout << "\nmatches std::stable_sort: " << (same ? "yes" : "no") << '\n';
    return 0;
}

Output (g++ 13.3 and clang++ 18.1.3, identical):

ascending:  5 10 13 14 22 29 37 41
descending: 41 37 29 22 14 13 10 5
strings:    apple date fig kiwi pear
list.sort:  5 10 13 14 22 29 37 41
by dept:    1:Cleo 1:Eli 2:Ava 2:Ben 2:Fay 3:Dev
matches std::stable_sort: yes

Only the left run and the part of the right run that was merged go through the buffer; the elements left over at the end of the right run are already in their final places. std::list::sort() in the demo is the list’s own merge sort. In libstdc++ it is bottom-up and relinks nodes through 64 scratch lists, so it never copies an element.

Java

// MergeSort.java - top-down merge sort in Java 21
import java.util.Arrays;

public class MergeSort {

    // Stable: on a tie the left element goes first.
    static void mergeSort(int[] a) {
        int[] buf = new int[a.length];       // one buffer for every merge
        sort(a, buf, 0, a.length);
    }

    private static void sort(int[] a, int[] buf, int lo, int hi) {   // [lo, hi)
        if (hi - lo < 2)
            return;
        int mid = lo + (hi - lo) / 2;        // or (lo + hi) >>> 1; never (lo + hi) / 2
        sort(a, buf, lo, mid);
        sort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi)
            buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
        while (i < mid) buf[k++] = a[i++];
        while (j < hi)  buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }

    public static void main(String[] args) {
        int[] data = {29, 10, 14, 37, 13, 5, 41, 22};
        mergeSort(data);
        System.out.println("Sorted: " + Arrays.toString(data));
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Java’s int arithmetic wraps on overflow instead of being undefined, so (lo + hi) / 2 there gives a negative index and an ArrayIndexOutOfBoundsException on a large enough array. (lo + hi) >>> 1, an unsigned shift, is the other common fix in Java.

Python

"""Top-down merge sort in Python 3."""


def merge_sort(a: list[int]) -> list[int]:
    """Return a new sorted list. Stable: on a tie the left element goes first."""
    if len(a) < 2:
        return list(a)
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if right[j] < left[i]:
            out.append(right[j])
            j += 1
        else:
            out.append(left[i])
            i += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


if __name__ == "__main__":
    data = [29, 10, 14, 37, 13, 5, 41, 22]
    print("Sorted:", merge_sort(data))

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

This version returns a new list and slices at every level, which is clear and allocates heavily. Python’s integers do not overflow, so the midpoint is not a concern here. sorted() is the right call in real code.

C#

// MergeSort.cs - top-down merge sort in C#
using System;

namespace MyCPlus.Sorting;

public static class MergeSort
{
    // Stable: on a tie the left element goes first.
    public static void Sort(int[] a)
    {
        int[] buf = new int[a.Length];       // one buffer for every merge
        SortRange(a, buf, 0, a.Length);
    }

    private static void SortRange(int[] a, int[] buf, int lo, int hi)   // [lo, hi)
    {
        if (hi - lo < 2)
            return;
        int mid = lo + (hi - lo) / 2;
        SortRange(a, buf, lo, mid);
        SortRange(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi)
            buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
        while (i < mid) buf[k++] = a[i++];
        while (j < hi) buf[k++] = a[j++];
        Array.Copy(buf, lo, a, lo, hi - lo);
    }
}

// Program.cs - sorts the article's array with MergeSort.Sort
using System;

namespace MyCPlus.Sorting;

public static class Program
{
    public static void Main()
    {
        int[] data = { 29, 10, 14, 37, 13, 5, 41, 22 };
        MergeSort.Sort(data);
        Console.WriteLine("Sorted: [" + string.Join(", ", data) + "]");
    }
}

Sorted: [5, 10, 13, 14, 22, 29, 37, 41]

Use the Library in Production

Timsort, used by Java and Python, is a merge sort that finds runs already in order, extends short ones with binary insertion sort, and merges runs with a strategy tuned for real data. The skip check measured above is the simplest form of the same idea.

Key Takeaways

• Merge sort’s worst case is its average case. The random input needed 120,346 comparisons, within 3% of the 123,617 worst-case bound for n = 10,000.
• Stability lives in one comparison. Taking from the right on ties still sorts and reverses equal keys.
• The skip-if-ordered check is a trade. It cut sorted input from 64,608 comparisons to 9,999 and cost 5.7% on random and 14% on reversed input.
• Allocate the buffer once. A malloc() per merge meant 999,999 calls and cost 11–14% here, and it moves out-of-memory handling into the middle of the sort.
• Compute the midpoint as lo + (hi - lo) / 2. (lo + hi) / 2 with int indices gave -397,483,648.
• Match the base case to the range convention. With half-open ranges, lo >= hi recursed forever: a crash at -O0, a hang at -O2.
• Merge sort counts inversions in O(n log n), matching a brute-force count exactly on all five 10,000-element inputs.

Frequently Asked Questions

Conclusion

Merge sort is the sort whose guarantees are easiest to state: n log n comparisons at most, equal keys kept in order, no bad inputs. What the measurements add is where its costs actually are. They are not in the comparisons, which barely move between inputs, but in the buffer, the copying, and in details such as a tie rule and a midpoint formula that each decide whether the guarantees hold at all.

The same merge that sorts can count inversions in passing, and merge-based designs such as Timsort are what sorted() and Java’s object sort run today. For the other side of the trade-off, sorting in place with no worst-case guarantee, see the quicksort algorithm article.

Source Code and Tests

The C code is in mycplus/c-examples/sorting/merge-sort and the C++ code in mycplus/cpp-examples/sorting/merge-sort . The Java, Python and C# versions are in mycplus/java-examples/sorting/merge-sort, mycplus/python-examples/sorting/merge-sort and mycplus/csharp-examples/sorting/merge-sort, each with its own tests and workflow.

Build and test either one with:

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

What the builds check on each change:

• Compilation with warnings as errors: GCC and Clang with -Wall -Wextra -pedantic -Werror (C11 and C17; C++17 and C++20), and MSVC with /W4 /WX.
• Correctness against a reference: both C array sorts against qsort(), the list sort against the sorted array, and count_inversions() against a brute-force count, on 20,000 random inputs of 0 to 64 elements including empty inputs, INT_MIN, INT_MAX and heavy duplication. The C++ template is checked against std::stable_sort on 5,000 inputs of (key, position) pairs, which checks stability as well as order.
• The output on this page: the example, the trace, both count tables, the tie-rule program and the C++ demo are compared with the output blocks above.
• Sanitizers: all tests run again under AddressSanitizer and UndefinedBehaviorSanitizer.
• The pitfalls: the build confirms that UBSan reports the midpoint overflow, that the wrong base case overflows the stack under AddressSanitizer at -O0, and that the allocate-per-merge version makes 999,999 allocations and produces the same result.

The builds do not run the timings, which depend on the machine. A green badge means the code compiles on those toolchains and passes those tests; it does not reproduce the timings above.