Merge Type in C, C++, Java, Python and C#: Code and Prices

Merge type is the one algorithm on this collection that’s each steady and O(n log n) on each enter. Its worst case is its common case. The prices sit elsewhere, and they’re simpler to measure than to guess. A standard one-line optimization minimize comparisons on sorted enter from 64,608 to 9,999, and added 14% on reversed enter. Allocating a buffer inside each merge made 999,999 calls to malloc() for one million components and value 11–14% of the working time, lower than its fame suggests.

This information traces merge type on a small array, then offers top-down, bottom-up and linked-list implementations in C, a generic C++ model, and variations in Java, Python and C#. It measures the comparisons in opposition to the worst-case certain and makes use of merge type to rely inversions. It closes with 4 errors, two of which behave in another way relying on the optimization stage. Each program was compiled and run for this text 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 (additionally checked with ruff and mypy --strict), and C# on .NET 10 with analyzer warnings as errors. All 5 type the identical array and print the identical outcome. The C and C++ code is in GitHub repositories whose builds run the exams on every change.

What Is Merge Type?

Merge type is a divide-and-conquer sorting algorithm that splits an array into two halves, types every half recursively, and merges the 2 sorted halves into one sorted run. The merge step does the work: it repeatedly takes the smaller of the 2 entrance components. Merge type makes O(n log n) comparisons on each enter, is steady, and desires O(n) additional reminiscence for arrays.

The merge is the place stability comes from. When the 2 entrance components are equal, taking the one from the left half retains equal keys of their unique order. That property is why merge type, moderately than quicksort, is the premise of the usual steady types: libstdc++’s std::stable_sort is a merge type with a short lived buffer, and Java’s object type and Python’s sorted() each use Timsort, a merge type that detects runs already so as.

How Merge Type Works

1. Break up the vary [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
complete comparisons: 16

Every stage touches all eight components as soon as, and there are log₂ 8 = 3 ranges. A merge of two runs of complete size m makes at most m − 1 comparisons, and no less than the size of the shorter run, which occurs when one run is exhausted earlier than the opposite is touched. Merging [10 14 29 37] with [5 13 22 41] wanted 7 comparisons, the utmost for 8 components, as a result of the values interleave all the way in which to the top. For any 8-element enter this merge makes between 12 and 17 comparisons in complete.

Merge Type in C

The header declares the 2 array types, a linked-list type and an inversion counter, all of that are in the identical supply file:

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

#embody <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 worth;
    struct node *subsequent;
};
struct node *list_merge_sort(struct node *head);   /* no buffer; O(log n) stack */

/* Variety of pairs i < j with a[i] > a[j]. Kinds a as a aspect impact.
 * Returns -1 (as unsigned lengthy lengthy: ULLONG_MAX) if malloc fails. */
unsigned lengthy lengthy count_inversions(int a[], size_t n);

#endif

/* merge_sort.c - merge type in C11.
 * SORT_LESS(x, y) means "x types earlier than y". Take a look at packages redefine it
 * earlier than together with this file, to rely comparisons. MERGE_SKIP_SORTED
 * (default 1) skips a merge when the 2 halves are already so as. */
#embody <stdlib.h>
#embody <string.h>
#embody "merge_sort.h"

#ifndef SORT_LESS
#outline SORT_LESS(x, y) ((x) < (y))
#endif
#ifndef MERGE_SKIP_SORTED
#outline 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 hello)
{
    size_t i = lo, j = mid, ok = lo;
    whereas (i < mid && j < hello)
        buf[k++] = SORT_LESS(a[j], a[i]) ? a[j++] : a[i++];
    whereas (i < mid) buf[k++] = a[i++];
    whereas (j < hello)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hello - lo) * sizeof a[0]);
}

/* Kinds the half-open vary a[lo..hi). */
static void merge_sort_rec(int a[], int buf[], size_t lo, size_t hello)
{
    if (hello - lo < 2)                         /* 0 or 1 component: sorted */
        return;
    size_t mid = lo + (hello - lo) / 2;         /* can not overflow */
    merge_sort_rec(a, buf, lo, mid);
    merge_sort_rec(a, buf, mid, hello);
    if (MERGE_SKIP_SORTED && !SORT_LESS(a[mid], a[mid - 1]))
        return;                              /* halves already so as */
    merge(a, buf, lo, mid, hello);
}

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

/* Backside-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 hello = (n - mid > width) ? mid + width : n;
            merge(a, buf, lo, mid, hello);
        }
    free(buf);
    return 0;
}

/* Linked record: cut up with gradual/quick pointers, merge by relinking nodes. */
static struct node *list_merge(struct node *x, struct node *y)
{
    struct node head = { 0, NULL }, *tail = &head;
    whereas (x != NULL && y != NULL) {
        if (SORT_LESS(y->worth, x->worth)) { tail->subsequent = y; y = y->subsequent; }
        else                               { tail->subsequent = x; x = x->subsequent; }
        tail = tail->subsequent;
    }
    tail->subsequent = (x != NULL) ? x : y;
    return head.subsequent;
}

struct node *list_merge_sort(struct node *head)
{
    if (head == NULL || head->subsequent == NULL)
        return head;
    struct node *gradual = head, *quick = head->subsequent;
    whereas (quick != NULL && fast->subsequent != NULL) {
        gradual = slow->subsequent;
        quick = fast->next->subsequent;
    }
    struct node *second = slow->subsequent;        /* minimize the record in two */
    slow->subsequent = NULL;
    return list_merge(list_merge_sort(head), list_merge_sort(second));
}

/* Inversion counting: when a component is taken from the proper run, it's
 * smaller than each component nonetheless ready within the left run. */
static unsigned lengthy lengthy count_rec(int a[], int buf[], size_t lo, size_t hello)
{
    if (hello - lo < 2)
        return 0;
    size_t mid = lo + (hello - lo) / 2;
    unsigned lengthy lengthy inv = count_rec(a, buf, lo, mid) + count_rec(a, buf, mid, hello);
    size_t i = lo, j = mid, ok = lo;
    whereas (i < mid && j < hello) {
        if (SORT_LESS(a[j], a[i])) {
            inv += mid - i;                  /* a[j] < a[i..mid) */
            buf[k++] = a[j++];
        } else {
            buf[k++] = a[i++];
        }
    }
    whereas (i < mid) buf[k++] = a[i++];
    whereas (j < hello)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hello - lo) * sizeof a[0]);
    return inv;
}

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

A program that calls all 4:

/* merge_example.c - arrays, a linked record, and inversion counting */
#embody <stdio.h>
#embody <limits.h>
#embody "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 major(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("earlier than:", a, n);
    if (merge_sort(a, n) != 0 || merge_sort_bottom_up(b, n) != 0) {
        fputs("out of memoryn", stderr);
        return 1;
    }
    print_array("top-down:", a, n);
    print_array("bottom-up:", b, n);

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

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

Output:

earlier than:     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
record:       5 10 13 14 22 29 37 41
inversions: 13
limits:     -2147483648 -1 0 0 2147483647

The alternatives within the C code:

• One buffer, allotted as soon as. merge_sort() allocates n integers earlier than recursing and each merge reuses them. It returns -1 if malloc() fails moderately 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 proper solely when that component is strictly smaller.
• The record model wants no buffer. It relinks nodes as an alternative of copying values. It nonetheless recurses, so it makes use of O(log n) stack.

Comparisons, Measured

The counting program types 10,000 values in 5 preparations (the identical 5, generated the identical manner, as within the insertion type article) and counts comparisons for the top-down and bottom-up variations. It additionally counts inversions with count_inversions() and checks the outcome in opposition to a brute-force O(n²) rely. The repository builds this system twice. First with the test that skips a merge when a[mid − 1] <= a[mid]:

Output:

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

after which with out it:

Output:

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

4 issues stand out:

• The worst-case certain holds. For top-down merge type the utmost is n⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1, which is 10,000 × 14 − 16,384 + 1 = 123,617 comparisons for n = 10,000. With out the skip test, the random enter wanted 120,346, inside 3% of that certain; merge type’s finest and worst differ by far lower than insertion type’s 9,999 and 49,995,000.
• The skip test is a commerce. When two halves are already so as, one comparability replaces an entire merge. That took sorted enter from 64,608 comparisons to 9,999, and saved 9% on the regionally shuffled enter and 16% on the enter with 100 far swaps. On random enter the test nearly by no means succeeds, so it added 6,806 comparisons (5.7%); on reversed enter it succeeds solely the place equal values meet, and added 9,973 (14%). Timsort, utilized by Java and Python, detects current order in a extra normal manner, discovering entire runs moderately than checking one pair per merge.
• Backside-up made a unique variety of comparisons, as a result of for n = 10,000, which isn’t an influence of two, its runs are cut up in another way: it doubles fastened widths from the left, leaving a brief ultimate run at every stage. It made 123,669 on random enter, simply above the top-down certain, which doesn’t apply to it.
• The inversion counts match the brute-force counts precisely on all 5 inputs, and match the inversion counts measured independently within the insertion type article: 25,183,572 for the random enter.

Counting inversions with merge type

An inversion is a pair i < j with a[i] > a[j]. Throughout a merge, when a component is taken from the proper run, it’s smaller than each component nonetheless ready within the left run, and every of these kinds one inversion with it. So count_rec() provides mid − i at that second, and the entire rely takes O(n log n) as an alternative of the O(n²) of checking each pair. On the ten,000-element inputs above, the brute-force loop made about 50 million comparisons per enter; the merge-based rely made not more than a merge type does.

How This Was Measured

No CPU pinning or frequency-scaling management was used, and all timings come from this one digital machine. The comparability counts above don’t rely on it.

Timings: High-Down, Backside-Up and qsort()

One run of the timing program constructed with GCC:

Output:

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

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

The 2 variations ran at about the identical pace on random enter. On sorted enter the top-down model completed in beneath 5 ms due to the skip test: it compares at every cut up and by no means merges. The underside-up model has no such test and nonetheless copied each component at each stage, though every merge was low cost. glibc’s qsort(), which is itself a merge type (see the Use the Library part), took about 1.5 to 2 instances so long as the hand-written model on random enter; it calls the comparator by means of a perform pointer on each comparability, which the hand-written model compiled with < inline doesn’t. That clarification is an inference: no profiler was run.

4 Merge Type Errors

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

The midpoint of two int indices overflows as soon as their sum passes INT_MAX, which occurs for any array over a couple of billion components. The arithmetic could be proven with out the array:

/* midpoint_overflow.c - (lo + hello) / 2 with int indices close to INT_MAX.
 * Wants no big array: the arithmetic is computed earlier than any entry. */
#embody <stdio.h>

static int mid_sum(int lo, int hello)  { return (lo + hello) / 2; }        /* overflows */
static int mid_diff(int lo, int hello) { return lo + (hello - lo) / 2; }   /* doesn't  */

int major(void)
{
    int lo = 1500000000, hello = 2000000000;    /* a variety inside a 2-billion array */
    printf("(lo + hello) / 2      = %dn", mid_sum(lo, hello));
    printf("lo + (hello - lo) / 2 = %dn", mid_diff(lo, hello));
    return 0;
}

Output (GCC and Clang, -O2):

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

Signed overflow is undefined conduct in C; right here it produced a adverse index, which an actual merge type would cross to a[mid]. UndefinedBehaviorSanitizer names it:

midpoint_overflow.c:5:50: runtime error: signed integer overflow: 1500000000 + 2000000000 can't be represented in sort 'int'

This precise bug in binary search and merge type code was the topic of Joshua Bloch’s 2006 put up Practically All Binary Searches and Mergesorts are Damaged. Use lo + (hello - lo) / 2, and size_t for indices.

2. The Incorrect 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 hello)
{
    if (lo >= hello)                            /* ought to be: hello - lo < 2 */
        return;
    size_t mid = lo + (hello - lo) / 2;
    sort_range(a, lo, mid);
    sort_range(a, mid, hello);
    /* no merge wanted to point out the bug: the calls above by no means return */
}

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

A one-element vary [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[], Merchandise buf[], size_t lo, size_t hello, int ties_right)
{
    if (hello - lo < 2)
        return;
    size_t mid = lo + (hello - lo) / 2;
    sort_items(a, buf, lo, mid, ties_right);
    sort_items(a, buf, mid, hello, ties_right);
    size_t i = lo, j = mid, ok = lo;
    whereas (i < mid && j < hello) {
        int take_right = ties_right ? a[j].key <= a[i].key    /* mistaken */
                                    : a[j].key <  a[i].key;   /* proper */
        buf[k++] = take_right ? a[j++] : a[i++];
    }
    whereas (i < mid) buf[k++] = a[i++];
    whereas (j < hello)  buf[k++] = a[j++];
    memcpy(a + lo, buf + lo, (hello - lo) * sizeof a[0]);
}

static void present(const char *label, const Merchandise a[], size_t n)
{
    printf("%s", label);
    for (size_t i = 0; i < n; i++)
        printf(" %dpercentc", a[i].key, a[i].tag);
    printf("n");
}

int major(void)
{
    Merchandise x[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} }, bx[5];
    Merchandise y[] = { {2,'a'}, {1,'b'}, {2,'c'}, {1,'d'}, {2,'e'} }, by[5];
    present("enter:           ", x, 5);
    sort_items(x, bx, 0, 5, 0);
    present("proper provided that <: ", x, 5);
    sort_items(y, by, 0, 5, 1);
    present("proper if <=:     ", y, 5);
    return 0;
}

Output:

enter:            2a 1b 2c 1d 2e
proper provided that <:  1b 1d 2a 2c 2e
proper if <=:      1d 1b 2e 2c 2a

Each are sorted by key, so a sortedness take a look at passes each. The second reversed each teams of equal keys, which removes the property most packages select merge type for.

4. Allocating Inside Each Merge

A standard first model allocates the non permanent array inside merge(). It really works, and it calls malloc() as soon as per merge: n − 1 instances.

/* malloc_per_merge.c - allocating a short lived array inside each merge.
 * It types accurately; rely the allocations and time it on 1,000,000 ints.
 * POSIX (clock_gettime). */
#outline _POSIX_C_SOURCE 199309L
#embody <stdio.h>
#embody <stdlib.h>
#embody <string.h>
#embody <time.h>

#outline N 1000000

static unsigned lengthy lengthy allocations;

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

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

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

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

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 major(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 memoryn", stderr); return 1; }
    unsigned lengthy lengthy 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) { places("outcomes 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 msn", allocations, ta[2]);
    printf("one buffer:       1 allocation, median %.1f msn", tb[2]);
    printf("outcomes identicaln");
    free(in); free(a); free(b); free(buf);
    return 0;
}

Output (GCC, certainly one of three runs):

malloc per merge: 999999 allocations, median 121.0 ms
one buffer:       1 allocation, median 108.2 ms
outcomes similar

Throughout three runs, one allocation per merge took 117–121 ms in opposition to 104–108 ms for one buffer with GCC, and 86–88 ms in opposition to 75–77 ms with Clang: about 11–14% slower. That’s lower than the decision rely suggests. The likeliest motive is that the majority merges are small and glibc’s allocator palms the identical small blocks again shortly after every free(); that’s an inference, not a measurement of the allocator. The primary model of this experiment timed every technique as soon as as an alternative of taking medians, and in certainly one of its runs the malloc model got here out quicker. Single runs couldn’t inform the 2 aside. The only buffer remains to be the proper design: it additionally makes out-of-memory a single test at first as an alternative of a failure that may happen in the midst of a form.

Merge Type Time and House Complexity

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

C++

The C++ template types any random-access vary with a comparator. Its buffer is a std::vector reserved as soon as; clear() retains the capability, so later merges don’t reallocate. Parts are moved, not copied, so it additionally types std::string and move-only sorts effectively:

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

#embody <useful>
#embody <iterator>
#embody <utility>
#embody <vector>

namespace element {

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

    buf.clear();                                 // capability is saved: no reallocation
    RandomIt i = first, j = mid;
    whereas (i != mid && j != final)
        buf.push_back(comp(*j, *i) ? std::transfer(*j++) : std::transfer(*i++));  // ties: left first
    whereas (i != mid)
        buf.push_back(std::transfer(*i++));
    std::transfer(buf.start(), buf.finish(), first);    // the remainder 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 Worker& a, const Worker& b) { return a.dept < b.dept; };
    merge_sort(employees.start(), employees.finish(), by_dept);
    std::stable_sort(anticipated.start(), anticipated.finish(), by_dept);
    std::cout << "by dept:   ";
    for (const auto& e : employees) std::cout << ' ' << e.dept << ':' << e.title;
    bool identical = std::equal(employees.start(), employees.finish(), anticipated.start(),
                           [](const Worker& a, const Worker& b) { return a.title == b.title; });
    std::cout << "nmatches std::stable_sort: " << (identical ? "sure" : "no") << 'n';
    return 0;
}

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

ascending:  5 10 13 14 22 29 37 41
descending: 41 37 29 22 14 13 10 5
strings:    apple date fig kiwi pear
record.type:  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: sure

Solely the left run and the a part of the proper run that was merged undergo the buffer; the weather left over on the finish of the proper run are already of their ultimate locations. std::record::type() within the demo is the record’s personal merge type. In libstdc++ it’s bottom-up and relinks nodes by means of 64 scratch lists, so it by no means copies a component.

Java

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

public class MergeSort {

    // Steady: on a tie the left component goes first.
    static void mergeSort(int[] a) {
        int[] buf = new int[a.length];       // one buffer for each merge
        type(a, buf, 0, a.size);
    }

    non-public static void type(int[] a, int[] buf, int lo, int hello) {   // [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++];
        whereas (i < mid) buf[k++] = a[i++];
        whereas (j < hello)  buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hello - lo);
    }

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

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

Java’s int arithmetic wraps on overflow as an alternative of being undefined, so (lo + hello) / 2 there offers a adverse index and an ArrayIndexOutOfBoundsException on a big sufficient array. (lo + hello) >>> 1, an unsigned shift, is the opposite widespread repair in Java.

Python

"""High-down merge type in Python 3."""


def merge_sort(a: record[int]) -> record[int]:
    """Return a brand new sorted record. Steady: on a tie the left component goes first."""
    if len(a) < 2:
        return record(a)
    mid = len(a) // 2
    left, proper = merge_sort(a[:mid]), merge_sort(a[mid:])
    out: record[int] = []
    i = j = 0
    whereas i < len(left) and j < len(proper):
        if proper[j] < left[i]:
            out.append(proper[j])
            j += 1
        else:
            out.append(left[i])
            i += 1
    out.lengthen(left[i:])
    out.lengthen(proper[j:])
    return out


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

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

This model returns a brand new record and slices at each stage, which is evident and allocates closely. Python’s integers don’t overflow, so the midpoint just isn’t a priority right here. sorted() is the proper name in actual code.

C#

// MergeSort.cs - top-down merge type in C#
utilizing System;

namespace MyCPlus.Sorting;

public static class MergeSort
{
    // Steady: on a tie the left component goes first.
    public static void Type(int[] a)
    {
        int[] buf = new int[a.Length];       // one buffer for each merge
        SortRange(a, buf, 0, a.Size);
    }

    non-public static void SortRange(int[] a, int[] buf, int lo, int hello)   // [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++];
        whereas (i < mid) buf[k++] = a[i++];
        whereas (j < hello) buf[k++] = a[j++];
        Array.Copy(buf, lo, a, lo, hello - lo);
    }
}

// Program.cs - types the article's array with MergeSort.Type
utilizing System;

namespace MyCPlus.Sorting;

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

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

Use the Library in Manufacturing

Timsort, utilized by Java and Python, is a merge type that finds runs already so as, extends brief ones with binary insertion type, and merges runs with a technique tuned for actual information. The skip test measured above is the best type of the identical concept.

Key Takeaways

• Merge type’s worst case is its common case. The random enter wanted 120,346 comparisons, inside 3% of the 123,617 worst-case certain for n = 10,000.
• Stability lives in a single comparability. Taking from the proper on ties nonetheless types and reverses equal keys.
• The skip-if-ordered test is a commerce. It minimize sorted enter from 64,608 comparisons to 9,999 and value 5.7% on random and 14% on reversed enter.
• Allocate the buffer as soon as. A malloc() per merge meant 999,999 calls and value 11–14% right here, and it strikes out-of-memory dealing with into the center of the kind.
• Compute the midpoint as lo + (hello - lo) / 2. (lo + hello) / 2 with int indices gave -397,483,648.
• Match the bottom case to the vary conference. With half-open ranges, lo >= hello recursed ceaselessly: a crash at -O0, a grasp at -O2.
• Merge type counts inversions in O(n log n), matching a brute-force rely precisely on all 5 10,000-element inputs.

Often Requested Questions

Conclusion

Merge type is the kind whose ensures are best to state: n log n comparisons at most, equal keys saved so as, no dangerous inputs. What the measurements add is the place its prices truly are. They aren’t within the comparisons, which barely transfer between inputs, however within the buffer, the copying, and in particulars reminiscent of a tie rule and a midpoint components that every determine whether or not the ensures maintain in any respect.

The identical merge that types can rely inversions in passing, and merge-based designs reminiscent of Timsort are what sorted() and Java’s object type run right this moment. For the opposite aspect of the trade-off, sorting in place with no worst-case assure, see the quicksort algorithm article.

Supply Code and Exams

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# variations are in mycplus/java-examples/sorting/merge-sort, mycplus/python-examples/sorting/merge-sort and mycplus/csharp-examples/sorting/merge-sort, every with its personal exams and workflow.

Construct and take a look at both one with:

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

What the builds test on every 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 in opposition to a reference: each C array types in opposition to qsort(), the record type in opposition to the sorted array, and count_inversions() in opposition to a brute-force rely, on 20,000 random inputs of 0 to 64 components together with empty inputs, INT_MIN, INT_MAX and heavy duplication. The C++ template is checked in opposition to std::stable_sort on 5,000 inputs of (key, place) pairs, which checks stability in addition to order.
• The output on this web page: the instance, the hint, each rely tables, the tie-rule program and the C++ demo are in contrast with the output blocks above.
• Sanitizers: all exams run once more beneath AddressSanitizer and UndefinedBehaviorSanitizer.
• The pitfalls: the construct confirms that UBSan stories the midpoint overflow, that the mistaken base case overflows the stack beneath AddressSanitizer at -O0, and that the allocate-per-merge model makes 999,999 allocations and produces the identical outcome.

The builds don’t run the timings, which rely on the machine. A inexperienced badge means the code compiles on these toolchains and passes these exams; it doesn’t reproduce the timings above.