Merge sort

In plain words

Two people each have a sorted pile of cards, with the smallest card on top. To make one sorted pile, you look at the two top cards. You take the smaller one and put it face down on a new pile. You do this again until both piles are empty. This step is a merge. It looks at each card one time.

Merge sort uses the merge to sort. It cuts the array into two halves. It sorts each half with the same method. Then it merges the two sorted halves. An array with one item is already sorted, so the method stops there.

See it run

MERGE-SORT(A, lo, hi) ▷ sort A[lo .. hi − 1]
1if hi − lo ≤ 1 then return
2mid ← lo + ⌊(hi − lo) / 2⌋
3MERGE-SORT(A, lo, mid)
4MERGE-SORT(A, mid, hi)
5MERGE(A, lo, mid, hi)
MERGE(A, lo, mid, hi) ▷ A[lo .. mid − 1] and A[mid .. hi − 1] are sorted
6B ← a copy of A[lo .. mid − 1]
7i ← 0, j ← mid, k ← lo
8while i < |B| and j < hi do
9if B[i] ≤ A[j] then A[k] ← B[i], i ← i + 1 ▷ ≤ keeps the sort stable
10else A[k] ← A[j], j ← j + 1
11k ← k + 1
12while i < |B| do
13A[k] ← B[i], i ← i + 1, k ← k + 1

0 / 0 Speed Input

Use your own input

Type the input as JSON, in the same form as a preset.

Open the full player

The problem

The input is an array $A[0 \ldots n-1]$ of items with a total order. The output is the same array, with its items in non-decreasing order. This is the sorting problem.

The algorithm

The call MERGE-SORT $(A, 0, n)$ sorts the full array. The range $[lo, hi)$ is half-open: it holds $A[lo \ldots hi-1]$ .

MERGE-SORT(A, lo, hi) ▷ sort A[lo .. hi − 1]
1if hi − lo ≤ 1 then return
2mid ← lo + ⌊(hi − lo) / 2⌋
3MERGE-SORT(A, lo, mid)
4MERGE-SORT(A, mid, hi)
5MERGE(A, lo, mid, hi)
MERGE(A, lo, mid, hi) ▷ A[lo .. mid − 1] and A[mid .. hi − 1] are sorted
6B ← a copy of A[lo .. mid − 1]
7i ← 0, j ← mid, k ← lo
8while i < |B| and j < hi do
9if B[i] ≤ A[j] then A[k] ← B[i], i ← i + 1 ▷ ≤ keeps the sort stable
10else A[k] ← A[j], j ← j + 1
11k ← k + 1
12while i < |B| do
13A[k] ← B[i], i ← i + 1, k ← k + 1

MERGE copies only the left half to a buffer $B$ . Then it fills $A$ from the left, with the smaller of $B[i]$ and $A[j]$ at each step. The write position $k$ never passes the read position $j$ , so no item of the right half is lost. When $B$ is empty, the rest of the right half is already in place. So the loop of line L12 only copies the rest of $B$ .

Example

Sort $A = [38, 27, 43, 3, 9, 82, 10]$ .

level	the parts
split	[38 27 43] [3 9 82 10]
split	[38] [27 43] [3 9] [82 10]
split	[38] [27] [43] [3] [9] [82] [10]
merge	[38] [27 43] [3 9] [10 82]
merge	[27 38 43] [3 9 10 82]
merge	[3 9 10 27 38 43 82]

In the last merge, $B = [27, 38, 43]$ and the right half is $[3, 9, 10, 82]$ . The merge takes 3, 9 and 10 from the right half, then 27, 38 and 43 from $B$ . The item 82 is already in place at the end.

Correctness

MERGE is correct by a loop invariant of line L8: $A[lo \ldots k-1]$ holds the $k - lo$ smallest items of the two halves, in sorted order, and $B[i]$ and $A[j]$ are the smallest items that are not yet placed. MERGE-SORT is then correct by induction on the length $hi - lo$ . A range of length 0 or 1 is sorted. For a longer range, both calls sort a shorter range, and MERGE makes one sorted range of the two. The full proof is below.

Proof: Merge sort sorts the array and keeps its itemsfull

We write $S$ for the multiset of the items of $A[lo \ldots hi-1]$ at the start of a call.

Lemma (MERGE). Assume that $lo \le mid \le hi$ , and that $A[lo \ldots mid-1]$ and $A[mid \ldots hi-1]$ are sorted. Then after MERGE $(A, lo, mid, hi)$ , $A[lo \ldots hi-1]$ is sorted and holds $S$ . No other item of $A$ changes.

Proof. Let $m = mid - lo$ . Line L6 makes $B = A[lo \ldots mid-1]$ , so $|B| = m$ . Line L7 sets $i = 0$ , $j = mid$ and $k = lo$ . We use this invariant for the loops of lines L8 and L12:

(M) $k = lo + i + (j - mid)$ . The part $A[lo \ldots k-1]$ holds $B[0 \ldots i-1]$ and the old $A[mid \ldots j-1]$ , in sorted order. Each item of $A[lo \ldots k-1]$ is at most each item of $B[i \ldots m-1]$ and at most each item of $A[j \ldots hi-1]$ . The part $A[j \ldots hi-1]$ is not changed.

At the start, $k = lo$ and the part is empty, so (M) is true. The first equation gives $k - j = lo + i - mid \le lo + m - mid = 0$ , so $k \le j$ . A write to $A[k]$ therefore never changes an item at an index of $j$ or more, before it is read.

In a step of line L8, both $B[i]$ and $A[j]$ exist. By (M) and because both parts are sorted, the smallest item that is not yet placed is $B[i]$ or $A[j]$ . Line L9 or line L10 writes the smaller one to $A[k]$ , so $A[lo \ldots k]$ is sorted and the third statement stays true. Line L11 and the update of $i$ or $j$ keep the first equation. If both items are equal, line L9 takes $B[i]$ , which comes from the left half.

The loop of line L8 stops when $i = m$ or $j = hi$ . If $i = m$ , then $k = j$ and the loop of line L12 does not run. The items $A[j \ldots hi-1]$ are in place: they are not changed, they are sorted, and by (M) they are at least each placed item. If $j = hi$ , the loop of line L12 copies $B[i \ldots m-1]$ to $A[k \ldots hi-1]$ in order, and each of these items is at least each placed item. In both cases $A[lo \ldots hi-1]$ is sorted, and it holds all of $B$ and all of the old right half, so it holds $S$ . $\square$

Theorem. After MERGE-SORT $(A, lo, hi)$ , the part $A[lo \ldots hi-1]$ is sorted and holds $S$ . No other item of $A$ changes.

Proof. By strong induction on $k = hi - lo$ . If $k \le 1$ , line L1 returns, and a part with at most one item is sorted. If $k \ge 2$ , line L2 gives $lo < mid < hi$ , so both calls of lines L3 and L4 have a shorter range. By the induction hypothesis, they sort $A[lo \ldots mid-1]$ and $A[mid \ldots hi-1]$ , and each call changes only its own part. The lemma then shows that line L5 makes $A[lo \ldots hi-1]$ sorted, with the items of $S$ . $\blacksquare$

Stability. Equal items in the same half keep their order by the induction hypothesis. For equal items in different halves, line L9 places the item of the left half first.

All proofs on one page

Complexity

Let $T(n)$ be the time on $n$ items. The two calls take $T(\lceil n/2 \rceil)$ and $T(\lfloor n/2 \rfloor)$ , and MERGE takes $\Theta(n)$ . So

$ $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n), \qquad T(1) = \Theta(1).$ $

The solution is $T(n) = \Theta(n \log n)$ . The recursion has $\lceil \lg n \rceil$ levels, and the merges of one level take $\Theta(n)$ time in total.

The number of comparisons is at most $n \lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1$ . This is at most $n \lg n$ .
The time is $\Theta(n \log n)$ in the best, the average and the worst case.
The extra space is $\Theta(n)$ for the buffer, and $\Theta(\log n)$ for the stack.

In the comparison model, each sort needs $\lg(n!) = n \lg n - \Theta(n)$ comparisons in the worst case. So merge sort is optimal in this model, up to a lower-order term.

Properties

Stable. Line L9 takes the item from the left half when the two items are equal.
Not in place. The buffer $B$ has up to $\lceil n/2 \rceil$ items. In-place merges exist, but they are complex and slow.
Not adaptive. This version does the same work on a sorted input. The natural variant below is adaptive.
Sequential access. MERGE reads and writes the items in order. So merge sort works well on linked lists, on tapes and on files that do not fit in memory.

Variants and improvements

Bottom-up merge sort. Merge parts of size 1, then 2, then 4, and so on. This needs no recursion.
A cut-off to insertion sort. Sort the small parts, of about 16 items, with insertion sort. This makes the program faster.
Skip a sorted merge. If $A[mid - 1] \le A[mid]$ , the two halves are already in order, and MERGE is not necessary. Then a sorted input takes $\Theta(n)$ time.
Natural merge sort and Timsort. Find the sorted runs that the input already has, and merge them. Timsort is the sort of Python and of Java for objects.
External merge sort. Sort parts that fit in memory, write them to disk, then merge many parts at a time.
Parallel merge sort. Run the two calls at the same time. With a parallel merge, the span is $O(\log^3 n)$ or less.

When to use it

Use merge sort when you need a stable sort with a guaranteed $O(n \log n)$ time. Use it to sort a linked list, because the merge needs no random access and no buffer there. Use it for data on disk. If you need a sort in place and stability is not necessary, heapsort or quicksort uses less memory.

Pitfalls

Comparing with <. The test $B[i] < A[j]$ in line L9 also sorts, but the sort is not stable.
A buffer in each call. A new buffer in each call of MERGE costs time. Allocate one buffer of $\lceil n/2 \rceil$ items, and pass it down.
Overflow of the midpoint. Use $lo + \lfloor (hi - lo)/2 \rfloor$ , not $\lfloor (lo + hi)/2 \rfloor$ .

Implementations

Each implementation follows the pseudocode above. A comment @line links a line of code to a line of the pseudocode. Point at a line of the pseudocode to see the matching code. The build runs the native tests of each language.

merge_sort.pytests passPage Raw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

from typing import Protocol, TypeVar


class Ordered(Protocol):
    def __lt__(self, other: "Ordered", /) -> bool: ...


T = TypeVar("T", bound=Ordered)


def merge_sort(a: list[T], lo: int = 0, hi: int | None = None) -> None:
    """Sort a[lo:hi] in place, in non-decreasing order. The sort is stable."""
    if hi is None:
        hi = len(a)
    if hi - lo <= 1:  # @line L1
        return
    mid = lo + (hi - lo) // 2  # @line L2
    merge_sort(a, lo, mid)  # @line L3
    merge_sort(a, mid, hi)  # @line L4
    merge(a, lo, mid, hi)  # @line L5


def merge(a: list[T], lo: int, mid: int, hi: int) -> None:
    """Merge the sorted parts a[lo:mid] and a[mid:hi] into one sorted part."""
    b = a[lo:mid]  # @line L6
    i, j, k = 0, mid, lo  # @line L7
    while i < len(b) and j < hi:  # @line L8
        if not a[j] < b[i]:  # @line L9: b[i] <= a[j], with only <
            a[k] = b[i]
            i += 1
        else:
            a[k] = a[j]  # @line L10
            j += 1
        k += 1  # @line L11
    while i < len(b):  # @line L12
        a[k] = b[i]  # @line L13
        i += 1
        k += 1

test_merge_sort.py 41 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

import random

from merge_sort import merge_sort


def test_example() -> None:
    a = [38, 27, 43, 3, 9, 82, 10]
    merge_sort(a)
    assert a == [3, 9, 10, 27, 38, 43, 82]


def test_edges() -> None:
    for a in ([], [1], [2, 1], [1, 1, 1], [3, 2, 1], [1, 2, 3]):
        b = list(a)
        merge_sort(b)
        assert b == sorted(a)


def test_stable() -> None:
    class Key:
        def __init__(self, k: int, tag: str) -> None:
            self.k, self.tag = k, tag

        def __lt__(self, other: "Key") -> bool:
            return self.k < other.k

    a = [Key(2, "a"), Key(1, "b"), Key(2, "c"), Key(1, "d"), Key(2, "e")]
    merge_sort(a)
    assert [x.tag for x in a] == ["b", "d", "a", "c", "e"]


def test_random_against_sorted() -> None:
    rng = random.Random(2150)
    for _ in range(500):
        a = [rng.randint(-50, 50) for _ in range(rng.randint(0, 60))]
        b = list(a)
        merge_sort(b)
        assert b == sorted(a)

merge_sort.hpptests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

#pragma once

#include <cstddef>
#include <span>
#include <utility>
#include <vector>

namespace algo {

namespace detail {

template <typename T>
void merge(std::span<T> a, std::size_t mid, std::vector<T>& b) {
    b.assign(std::make_move_iterator(a.begin()), std::make_move_iterator(a.begin() + mid));  // @line L6
    std::size_t i = 0, j = mid, k = 0;                       // @line L7
    while (i < b.size() && j < a.size()) {                   // @line L8
        if (!(a[j] < b[i])) {                                // @line L9: b[i] <= a[j], with only <
            a[k] = std::move(b[i++]);
        } else {
            a[k] = std::move(a[j++]);                        // @line L10
        }
        k++;                                                 // @line L11
    }
    while (i < b.size()) {                                   // @line L12
        a[k++] = std::move(b[i++]);                          // @line L13
    }
}

template <typename T>
void sort(std::span<T> a, std::vector<T>& b) {
    if (a.size() <= 1) return;                               // @line L1
    std::size_t mid = a.size() / 2;                          // @line L2
    sort(a.first(mid), b);                                   // @line L3
    sort(a.subspan(mid), b);                                 // @line L4
    merge(a, mid, b);                                        // @line L5
}

}  // namespace detail

// merge_sort sorts a in place, in non-decreasing order. The sort is stable.
template <typename T>
void merge_sort(std::span<T> a) {
    std::vector<T> b;
    b.reserve((a.size() + 1) / 2);
    detail::sort(a, b);
}

}  // namespace algo

test_merge_sort.cpp 41 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <utility>
#include <vector>

#include "merge_sort.hpp"

struct Item {
    int key;
    char tag;
    bool operator<(const Item& o) const { return key < o.key; }
};

int main() {
    std::vector<int> a{38, 27, 43, 3, 9, 82, 10};
    algo::merge_sort(std::span<int>(a));
    assert((a == std::vector<int>{3, 9, 10, 27, 38, 43, 82}));

    std::vector<Item> s{{2, 'a'}, {1, 'b'}, {2, 'c'}, {1, 'd'}, {2, 'e'}};
    algo::merge_sort(std::span<Item>(s));
    std::string tags;
    for (const auto& x : s) tags += x.tag;
    assert(tags == "bdace");

    std::mt19937 rng(2150);
    for (int t = 0; t < 500; t++) {
        std::vector<int> b(rng() % 61);
        for (auto& v : b) v = static_cast<int>(rng() % 101) - 50;
        auto want = b;
        algo::merge_sort(std::span<int>(b));
        std::ranges::sort(want);
        assert(b == want);
    }
    std::cout << "ok\n";
}

MergeSort.javaPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

/** Merge sort. */
public final class MergeSort {
    private MergeSort() {}

    /** Sorts a in place, in non-decreasing order. */
    public static void sort(long[] a) {
        long[] b = new long[(a.length + 1) / 2];
        sort(a, 0, a.length, b);
    }

    private static void sort(long[] a, int lo, int hi, long[] b) {
        if (hi - lo <= 1) return;                 // @line L1
        int mid = lo + (hi - lo) / 2;             // @line L2
        sort(a, lo, mid, b);                      // @line L3
        sort(a, mid, hi, b);                      // @line L4
        merge(a, lo, mid, hi, b);                 // @line L5
    }

    private static void merge(long[] a, int lo, int mid, int hi, long[] b) {
        int m = mid - lo;
        System.arraycopy(a, lo, b, 0, m);         // @line L6
        int i = 0, j = mid, k = lo;               // @line L7
        while (i < m && j < hi) {                 // @line L8
            if (b[i] <= a[j]) {                   // @line L9
                a[k] = b[i++];
            } else {
                a[k] = a[j++];                    // @line L10
            }
            k++;                                  // @line L11
        }
        while (i < m) {                           // @line L12
            a[k++] = b[i++];                      // @line L13
        }
    }
}

MergeSortTest.java 40 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

import java.util.Arrays;
import java.util.Random;
import org.junit.jupiter.api.Test;

class MergeSortTest {
    @Test
    void example() {
        long[] a = {38, 27, 43, 3, 9, 82, 10};
        MergeSort.sort(a);
        assertArrayEquals(new long[] {3, 9, 10, 27, 38, 43, 82}, a);
    }

    @Test
    void edges() {
        for (long[] a : new long[][] {{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}}) {
            long[] want = a.clone();
            Arrays.sort(want);
            MergeSort.sort(a);
            assertArrayEquals(want, a);
        }
    }

    @Test
    void randomAgainstArraysSort() {
        Random rng = new Random(2150);
        for (int t = 0; t < 500; t++) {
            long[] a = new long[rng.nextInt(61)];
            for (int i = 0; i < a.length; i++) a[i] = rng.nextInt(101) - 50;
            long[] want = a.clone();
            Arrays.sort(want);
            MergeSort.sort(a);
            assertArrayEquals(want, a);
        }
    }
}

merge_sort.ctests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

#include "merge_sort.h"

#include <stdlib.h>
#include <string.h>

static void merge(int64_t *a, size_t lo, size_t mid, size_t hi, int64_t *b) {
    size_t m = mid - lo;
    memcpy(b, a + lo, m * sizeof *b);           // @line L6
    size_t i = 0, j = mid, k = lo;              // @line L7
    while (i < m && j < hi) {                   // @line L8
        if (b[i] <= a[j]) {                     // @line L9
            a[k] = b[i++];
        } else {
            a[k] = a[j++];                      // @line L10
        }
        k++;                                    // @line L11
    }
    while (i < m) {                             // @line L12
        a[k++] = b[i++];                        // @line L13
    }
}

static void sort(int64_t *a, size_t lo, size_t hi, int64_t *b) {
    if (hi - lo <= 1) return;                   // @line L1
    size_t mid = lo + (hi - lo) / 2;            // @line L2
    sort(a, lo, mid, b);                        // @line L3
    sort(a, mid, hi, b);                        // @line L4
    merge(a, lo, mid, hi, b);                   // @line L5
}

bool merge_sort(int64_t *a, size_t n) {
    if (n <= 1) return true;
    int64_t *b = malloc((n + 1) / 2 * sizeof *b);
    if (b == NULL) return false;
    sort(a, 0, n, b);
    free(b);
    return true;
}

merge_sort.h 15 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

#ifndef MERGE_SORT_H
#define MERGE_SORT_H

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

// merge_sort sorts a[0..n-1] in place, in non-decreasing order. The sort is stable.
// It returns false, and does not change a, when it cannot allocate the buffer.
bool merge_sort(int64_t *a, size_t n);

#endif

test_merge_sort.c 34 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "merge_sort.h"

static int cmp(const void *p, const void *q) {
    int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
    return (a > b) - (a < b);
}

int main(void) {
    int64_t a[] = {38, 27, 43, 3, 9, 82, 10};
    const int64_t want[] = {3, 9, 10, 27, 38, 43, 82};
    assert(merge_sort(a, 7));
    assert(memcmp(a, want, sizeof a) == 0);
    assert(merge_sort(NULL, 0));

    srand(2150);
    int64_t b[60], c[60];
    for (int t = 0; t < 500; t++) {
        size_t n = (size_t)(rand() % 61);
        for (size_t i = 0; i < n; i++) b[i] = c[i] = rand() % 101 - 50;
        assert(merge_sort(b, n));
        qsort(c, n, sizeof c[0], cmp);
        assert(n == 0 || memcmp(b, c, n * sizeof b[0]) == 0);
    }
    puts("ok");
    return 0;
}

MergeSort.csPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

namespace Algorithm;

/// <summary>Merge sort.</summary>
public static class MergeSort
{
    /// <summary>Sorts a in place, in non-decreasing order. The sort is stable.</summary>
    public static void Sort<T>(Span<T> a) where T : IComparable<T>
    {
        var b = new T[(a.Length + 1) / 2];
        Sort(a, b);
    }

    private static void Sort<T>(Span<T> a, T[] b) where T : IComparable<T>
    {
        if (a.Length <= 1) return;                      // @line L1
        int mid = a.Length / 2;                         // @line L2
        Sort(a[..mid], b);                              // @line L3
        Sort(a[mid..], b);                              // @line L4
        Merge(a, mid, b);                               // @line L5
    }

    private static void Merge<T>(Span<T> a, int mid, T[] b) where T : IComparable<T>
    {
        a[..mid].CopyTo(b);                             // @line L6
        int i = 0, j = mid, k = 0;                      // @line L7
        while (i < mid && j < a.Length)                 // @line L8
        {
            if (b[i].CompareTo(a[j]) <= 0)              // @line L9
            {
                a[k] = b[i++];
            }
            else
            {
                a[k] = a[j++];                          // @line L10
            }
            k++;                                        // @line L11
        }
        while (i < mid)                                 // @line L12
        {
            a[k++] = b[i++];                            // @line L13
        }
    }
}

MergeSortTests.cs 43 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

using Algorithm;
using Xunit;

public class MergeSortTests
{
    [Fact]
    public void Example()
    {
        long[] a = [38, 27, 43, 3, 9, 82, 10];
        MergeSort.Sort<long>(a);
        Assert.Equal(new long[] { 3, 9, 10, 27, 38, 43, 82 }, a);
    }

    [Fact]
    public void Edges()
    {
        foreach (var a in new[] { new long[] { }, new long[] { 1 }, new long[] { 2, 1 }, new long[] { 1, 1, 1 }, new long[] { 3, 2, 1 } })
        {
            var want = (long[])a.Clone();
            Array.Sort(want);
            MergeSort.Sort<long>(a);
            Assert.Equal(want, a);
        }
    }

    [Fact]
    public void RandomAgainstArraySort()
    {
        var rng = new Random(2150);
        for (int t = 0; t < 500; t++)
        {
            var a = new long[rng.Next(61)];
            for (int i = 0; i < a.Length; i++) a[i] = rng.Next(101) - 50;
            var want = (long[])a.Clone();
            Array.Sort(want);
            MergeSort.Sort<long>(a);
            Assert.Equal(want, a);
        }
    }
}

mergeSort.jstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

/**
 * Sorts a in place, in non-decreasing order, and returns it. The sort is stable.
 * @template T
 * @param {T[]} a
 * @returns {T[]}
 */
export function mergeSort(a) {
  sort(a, 0, a.length);
  return a;
}

function sort(a, lo, hi) {
  if (hi - lo <= 1) return; // @line L1
  const mid = lo + ((hi - lo) >> 1); // @line L2
  sort(a, lo, mid); // @line L3
  sort(a, mid, hi); // @line L4
  merge(a, lo, mid, hi); // @line L5
}

function merge(a, lo, mid, hi) {
  const b = a.slice(lo, mid); // @line L6
  let i = 0, j = mid, k = lo; // @line L7
  while (i < b.length && j < hi) { // @line L8
    if (b[i] <= a[j]) { // @line L9
      a[k] = b[i++];
    } else {
      a[k] = a[j++]; // @line L10
    }
    k++; // @line L11
  }
  while (i < b.length) { // @line L12
    a[k++] = b[i++]; // @line L13
  }
}

mergeSort.test.js 30 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { mergeSort } from "./mergeSort.js";

test("example", () => {
  assert.deepEqual(mergeSort([38, 27, 43, 3, 9, 82, 10]), [3, 9, 10, 27, 38, 43, 82]);
});

test("edges", () => {
  assert.deepEqual(mergeSort([]), []);
  assert.deepEqual(mergeSort([1]), [1]);
  assert.deepEqual(mergeSort([3, 2, 1, 1]), [1, 1, 2, 3]);
  assert.deepEqual(mergeSort(["pear", "fig", "apple"]), ["apple", "fig", "pear"]);
});

test("random against Array.prototype.sort", () => {
  let s = 2150;
  const next = (m) => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 500; t++) {
    const a = Array.from({ length: next(61) }, () => next(101) - 50);
    const want = [...a].sort((p, q) => p - q);
    assert.deepEqual(mergeSort([...a]), want);
  }
});

mergeSort.tstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

/** Sorts a in place, in non-decreasing order, and returns it. The sort is stable. */
export function mergeSort<T extends number | string>(a: T[]): T[] {
  sort(a, 0, a.length);
  return a;
}

function sort<T extends number | string>(a: T[], lo: number, hi: number): void {
  if (hi - lo <= 1) return; // @line L1
  const mid = lo + ((hi - lo) >> 1); // @line L2
  sort(a, lo, mid); // @line L3
  sort(a, mid, hi); // @line L4
  merge(a, lo, mid, hi); // @line L5
}

function merge<T extends number | string>(a: T[], lo: number, mid: number, hi: number): void {
  const b = a.slice(lo, mid); // @line L6
  let i = 0, j = mid, k = lo; // @line L7
  while (i < b.length && j < hi) { // @line L8
    if (b[i] <= a[j]) { // @line L9
      a[k] = b[i++];
    } else {
      a[k] = a[j++]; // @line L10
    }
    k++; // @line L11
  }
  while (i < b.length) { // @line L12
    a[k++] = b[i++]; // @line L13
  }
}

mergeSort.test.ts 30 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

import { test } from "node:test";
import assert from "node:assert/strict";
import { mergeSort } from "./mergeSort.ts";

test("example", () => {
  assert.deepEqual(mergeSort([38, 27, 43, 3, 9, 82, 10]), [3, 9, 10, 27, 38, 43, 82]);
});

test("edges", () => {
  assert.deepEqual(mergeSort([]), []);
  assert.deepEqual(mergeSort([1]), [1]);
  assert.deepEqual(mergeSort([3, 2, 1, 1]), [1, 1, 2, 3]);
  assert.deepEqual(mergeSort(["pear", "fig", "apple"]), ["apple", "fig", "pear"]);
});

test("random against Array.prototype.sort", () => {
  let s = 2150;
  const next = (m: number): number => {
    s = (Math.imul(s, 1103515245) + 12345) >>> 0;
    return (s >>> 8) % m;
  };
  for (let t = 0; t < 500; t++) {
    const a = Array.from({ length: next(61) }, () => next(101) - 50);
    const want = [...a].sort((p, q) => p - q);
    assert.deepEqual(mergeSort([...a]), want);
  }
});

merge_sort.gotests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

// Package mergesort sorts a slice by merging.
package mergesort

import "cmp"

// Sort sorts a in place, in non-decreasing order. The sort is stable.
func Sort[T cmp.Ordered](a []T) {
	buf := make([]T, (len(a)+1)/2)
	sort(a, 0, len(a), buf)
}

func sort[T cmp.Ordered](a []T, lo, hi int, buf []T) {
	if hi-lo <= 1 { // @line L1
		return
	}
	mid := lo + (hi-lo)/2 // @line L2
	sort(a, lo, mid, buf)  // @line L3
	sort(a, mid, hi, buf)  // @line L4
	merge(a, lo, mid, hi, buf) // @line L5
}

func merge[T cmp.Ordered](a []T, lo, mid, hi int, buf []T) {
	b := buf[:mid-lo]
	copy(b, a[lo:mid])     // @line L6
	i, j, k := 0, mid, lo  // @line L7
	for i < len(b) && j < hi { // @line L8
		if b[i] <= a[j] { // @line L9
			a[k] = b[i]
			i++
		} else {
			a[k] = a[j] // @line L10
			j++
		}
		k++ // @line L11
	}
	for i < len(b) { // @line L12
		a[k] = b[i] // @line L13
		i++
		k++
	}
}

merge_sort_test.go 44 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

package mergesort

import (
	"math/rand/v2"
	"slices"
	"testing"
)

func TestExample(t *testing.T) {
	a := []int{38, 27, 43, 3, 9, 82, 10}
	Sort(a)
	if !slices.Equal(a, []int{3, 9, 10, 27, 38, 43, 82}) {
		t.Errorf("got %v", a)
	}
}

func TestEdges(t *testing.T) {
	for _, a := range [][]int{{}, {1}, {2, 1}, {1, 1, 1}, {3, 2, 1}, {1, 2, 3}} {
		b := slices.Clone(a)
		Sort(b)
		if !slices.IsSorted(b) {
			t.Errorf("Sort(%v) = %v", a, b)
		}
	}
}

func TestRandom(t *testing.T) {
	r := rand.New(rand.NewPCG(2150, 0))
	for range 500 {
		a := make([]int, r.IntN(61))
		for i := range a {
			a[i] = r.IntN(101) - 50
		}
		b, want := slices.Clone(a), slices.Clone(a)
		Sort(b)
		slices.Sort(want)
		if !slices.Equal(b, want) {
			t.Fatalf("Sort(%v) = %v", a, b)
		}
	}
}

merge_sort.rstests passPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

//! Merge sort.

/// Sorts `a` in place, in non-decreasing order. The sort is stable.
pub fn merge_sort<T: Ord + Clone>(a: &mut [T]) {
    let mut buf = Vec::with_capacity(a.len().div_ceil(2));
    sort(a, &mut buf);
}

fn sort<T: Ord + Clone>(a: &mut [T], buf: &mut Vec<T>) {
    let n = a.len();
    if n <= 1 {
        // @line L1
        return;
    }
    let mid = n / 2; // @line L2
    sort(&mut a[..mid], buf); // @line L3
    sort(&mut a[mid..], buf); // @line L4
    merge(a, mid, buf); // @line L5
}

fn merge<T: Ord + Clone>(a: &mut [T], mid: usize, buf: &mut Vec<T>) {
    buf.clear();
    buf.extend_from_slice(&a[..mid]); // @line L6
    let (mut i, mut j, mut k) = (0, mid, 0); // @line L7
    while i < buf.len() && j < a.len() {
        // @line L8
        if buf[i] <= a[j] {
            // @line L9
            a[k] = buf[i].clone();
            i += 1;
        } else {
            a[k] = a[j].clone(); // @line L10
            j += 1;
        }
        k += 1; // @line L11
    }
    while i < buf.len() {
        // @line L12
        a[k] = buf[i].clone(); // @line L13
        i += 1;
        k += 1;
    }
}

merge_sort_test.rs 55 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

use algo_merge_sort::merge_sort;

#[test]
fn example() {
    let mut a = [38, 27, 43, 3, 9, 82, 10];
    merge_sort(&mut a);
    assert_eq!(a, [3, 9, 10, 27, 38, 43, 82]);
}

#[test]
fn stable() {
    #[derive(Clone, Debug)]
    struct K(i32, char);
    impl PartialEq for K {
        fn eq(&self, o: &Self) -> bool {
            self.0 == o.0
        }
    }
    impl Eq for K {}
    impl PartialOrd for K {
        fn partial_cmp(&self, o: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(o))
        }
    }
    impl Ord for K {
        fn cmp(&self, o: &Self) -> std::cmp::Ordering {
            self.0.cmp(&o.0)
        }
    }
    let mut a = vec![K(2, 'a'), K(1, 'b'), K(2, 'c'), K(1, 'd'), K(2, 'e')];
    merge_sort(&mut a);
    let tags: String = a.iter().map(|k| k.1).collect();
    assert_eq!(tags, "bdace");
}

#[test]
fn random_against_std() {
    let mut s: u64 = 2150;
    let mut next = |m: u64| {
        s = s.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
        (s >> 33) % m
    };
    for _ in 0..500 {
        let n = next(61) as usize;
        let a: Vec<i64> = (0..n).map(|_| next(101) as i64 - 50).collect();
        let mut b = a.clone();
        let mut want = a.clone();
        merge_sort(&mut b);
        want.sort();
        assert_eq!(b, want);
    }
}

MergeSort.ktPage Raw GitHub

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

/** Sorts a in place, in non-decreasing order. The sort is stable. */
fun <T : Comparable<T>> mergeSort(a: MutableList<T>) {
    sort(a, 0, a.size)
}

private fun <T : Comparable<T>> sort(a: MutableList<T>, lo: Int, hi: Int) {
    if (hi - lo <= 1) return // @line L1
    val mid = lo + (hi - lo) / 2 // @line L2
    sort(a, lo, mid) // @line L3
    sort(a, mid, hi) // @line L4
    merge(a, lo, mid, hi) // @line L5
}

private fun <T : Comparable<T>> merge(a: MutableList<T>, lo: Int, mid: Int, hi: Int) {
    val b = a.subList(lo, mid).toList() // @line L6
    var i = 0 // @line L7
    var j = mid
    var k = lo
    while (i < b.size && j < hi) { // @line L8
        if (b[i] <= a[j]) { // @line L9
            a[k] = b[i++]
        } else {
            a[k] = a[j++] // @line L10
        }
        k++ // @line L11
    }
    while (i < b.size) { // @line L12
        a[k++] = b[i++] // @line L13
    }
}

MergeSortTest.kt 35 lines

// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.

import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class MergeSortTest {
    @Test
    fun example() {
        val a = mutableListOf(38, 27, 43, 3, 9, 82, 10)
        mergeSort(a)
        assertEquals(listOf(3, 9, 10, 27, 38, 43, 82), a)
    }

    @Test
    fun edges() {
        for (a in listOf(listOf(), listOf(1), listOf(2, 1), listOf(1, 1, 1), listOf(3, 2, 1))) {
            val b = a.toMutableList()
            mergeSort(b)
            assertEquals(a.sorted(), b)
        }
    }

    @Test
    fun randomAgainstSorted() {
        val rng = Random(2150)
        repeat(500) {
            val a = MutableList(rng.nextInt(61)) { rng.nextInt(101) - 50 }
            val want = a.sorted()
            mergeSort(a)
            assertEquals(want, a)
        }
    }
}

History

John von Neumann wrote a merge sort program for the EDVAC computer in 1945. Knuth gives this as one of the first programs written for a stored-program computer. Goldstine and von Neumann described the method in a report in 1948.

References

Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, Section 2.3
Donald E. Knuth, The Art of Computer Programming, Volume 3, second edition, Section 5.2.4

Ladder	Level	What the next level needs
Human proof		a full proof of time.average a full proof of time.best a full proof of time.worst a full proof of space.extra
Lean		name a Lean module in the lean field (07)
Code (c)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (cpp)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (csharp)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (go)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (java)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (javascript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (kotlin)		the native tests did not run in this build I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (python)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (rust)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Code (typescript)		I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work
Visual		V2 needs the oracle check V03, line-trace agreement V06, the counter check V07 and the budgets V08 (10.8.2)
Writing		the lead paragraph