Merge Sort in Python, Java and TypeScript

A top-down merge sort with one shared buffer, printing each merge.

A top-down merge sort is three functions: an entry point that allocates one buffer the length of the array, a recursive function that sorts the range from low up to but not including high by sorting its two halves and merging them, and the merge itself. The listings below print each merge as it happens, the two halves and what they became, and finish by checking the result against the language's built-in sort. Each runs on 5 2 7 4 1 8 3 6.

Merge sort with a shared buffer, printing each merge, in each language

merge_sort_code.pypy

def merge_sort(items: list[int]) -> None:
    buffer = [0] * len(items)
    sort_range(items, buffer, 0, len(items))


def sort_range(items: list[int], buffer: list[int], low: int, high: int) -> None:
    if high - low < 2:
        return
    mid = (low + high) // 2
    sort_range(items, buffer, low, mid)
    sort_range(items, buffer, mid, high)
    merge(items, buffer, low, mid, high)


def merge(items: list[int], buffer: list[int], low: int, mid: int, high: int) -> None:
    buffer[low:high] = items[low:high]
    i, j, k = low, mid, low
    while i < mid and j < high:
        if buffer[i] <= buffer[j]:
            items[k] = buffer[i]
            i += 1
        else:
            items[k] = buffer[j]
            j += 1
        k += 1
    while i < mid:
        items[k] = buffer[i]
        i += 1
        k += 1
    while j < high:
        items[k] = buffer[j]
        j += 1
        k += 1
    left = " ".join(map(str, buffer[low:mid]))
    right = " ".join(map(str, buffer[mid:high]))
    print(f"merge {left} | {right} -> {' '.join(map(str, items[low:high]))}")


numbers = [5, 2, 7, 4, 1, 8, 3, 6]
merge_sort(numbers)
print("sorted:", " ".join(map(str, numbers)))
print("built-in:", " ".join(map(str, sorted([5, 2, 7, 4, 1, 8, 3, 6]))))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

merge 5 | 2 -> 2 5
merge 7 | 4 -> 4 7
merge 2 5 | 4 7 -> 2 4 5 7
merge 1 | 8 -> 1 8
merge 3 | 6 -> 3 6
merge 1 8 | 3 6 -> 1 3 6 8
merge 2 4 5 7 | 1 3 6 8 -> 1 2 3 4 5 6 7 8
sorted: 1 2 3 4 5 6 7 8
built-in: 1 2 3 4 5 6 7 8

MergeSortCode.javajava

import java.util.Arrays;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class MergeSortCode {
    static void mergeSort(int[] items) {
        int[] buffer = new int[items.length];
        sortRange(items, buffer, 0, items.length);
    }

    static void sortRange(int[] items, int[] buffer, int low, int high) {
        if (high - low < 2) {
            return;
        }
        int mid = low + (high - low) / 2;
        sortRange(items, buffer, low, mid);
        sortRange(items, buffer, mid, high);
        merge(items, buffer, low, mid, high);
    }

    static void merge(int[] items, int[] buffer, int low, int mid, int high) {
        System.arraycopy(items, low, buffer, low, high - low);
        int i = low, j = mid, k = low;
        while (i < mid && j < high) {
            if (buffer[i] <= buffer[j]) {
                items[k++] = buffer[i++];
            } else {
                items[k++] = buffer[j++];
            }
        }
        while (i < mid) {
            items[k++] = buffer[i++];
        }
        while (j < high) {
            items[k++] = buffer[j++];
        }
        System.out.println("merge " + join(buffer, low, mid) + " | " + join(buffer, mid, high)
                + " -> " + join(items, low, high));
    }

    static String join(int[] values, int from, int to) {
        return IntStream.range(from, to).mapToObj(index -> String.valueOf(values[index]))
                .collect(Collectors.joining(" "));
    }

    public static void main(String[] args) {
        int[] numbers = {5, 2, 7, 4, 1, 8, 3, 6};
        mergeSort(numbers);
        System.out.println("sorted: " + join(numbers, 0, numbers.length));
        int[] copy = {5, 2, 7, 4, 1, 8, 3, 6};
        Arrays.sort(copy);
        System.out.println("built-in: " + join(copy, 0, copy.length));
    }
}

OutputRan with eclipse-temurin:25.0.4.1_1-jdk-noble (Java 25.0.4.1)

merge 5 | 2 -> 2 5
merge 7 | 4 -> 4 7
merge 2 5 | 4 7 -> 2 4 5 7
merge 1 | 8 -> 1 8
merge 3 | 6 -> 3 6
merge 1 8 | 3 6 -> 1 3 6 8
merge 2 4 5 7 | 1 3 6 8 -> 1 2 3 4 5 6 7 8
sorted: 1 2 3 4 5 6 7 8
built-in: 1 2 3 4 5 6 7 8

merge_sort_code.tsts

function mergeSort(items: number[]): void {
  const buffer = new Array<number>(items.length);
  sortRange(items, buffer, 0, items.length);
}

function sortRange(items: number[], buffer: number[], low: number, high: number): void {
  if (high - low < 2) {
    return;
  }
  const mid = Math.floor((low + high) / 2);
  sortRange(items, buffer, low, mid);
  sortRange(items, buffer, mid, high);
  merge(items, buffer, low, mid, high);
}

function merge(items: number[], buffer: number[], low: number, mid: number, high: number): void {
  for (let index = low; index < high; index++) {
    buffer[index] = items[index];
  }
  let i = low;
  let j = mid;
  let k = low;
  while (i < mid && j < high) {
    if (buffer[i] <= buffer[j]) {
      items[k++] = buffer[i++];
    } else {
      items[k++] = buffer[j++];
    }
  }
  while (i < mid) {
    items[k++] = buffer[i++];
  }
  while (j < high) {
    items[k++] = buffer[j++];
  }
  const left = buffer.slice(low, mid).join(" ");
  const right = buffer.slice(mid, high).join(" ");
  console.log(`merge ${left} | ${right} -> ${items.slice(low, high).join(" ")}`);
}

const numbers = [5, 2, 7, 4, 1, 8, 3, 6];
mergeSort(numbers);
console.log(`sorted: ${numbers.join(" ")}`);
const builtIn = [5, 2, 7, 4, 1, 8, 3, 6].sort((a, b) => a - b);
console.log(`built-in: ${builtIn.join(" ")}`);

OutputRan with node:24.22.0-trixie-slim (Node 24.22.0), TypeScript 5.9.3

merge 5 | 2 -> 2 5
merge 7 | 4 -> 4 7
merge 2 5 | 4 7 -> 2 4 5 7
merge 1 | 8 -> 1 8
merge 3 | 6 -> 3 6
merge 1 8 | 3 6 -> 1 3 6 8
merge 2 4 5 7 | 1 3 6 8 -> 1 2 3 4 5 6 7 8
sorted: 1 2 3 4 5 6 7 8
built-in: 1 2 3 4 5 6 7 8

All three printed the same nine lines, and the seven merges are the tree of splits read from the bottom up, left side first. The highlighted lines are the ones that matter. The first allocates the buffer once, in the entry point, and every merge reuses it. The second copies the range being merged into the buffer, so the merge can read the two halves from the copy while it writes the result over the original. The third is the comparison, <=, which takes from the left half on a tie and keeps the sort stable.

Allocating inside the merge is the common way to write this, and it works, but it creates a new array on every one of the n − 1 merges, which is a lot of short-lived memory for the garbage collector. Slicing the halves before recursing, items[:mid] in Python, costs the same again. One shared buffer keeps the extra space at a single O(n) array however the calls nest. The ranges are half-open, low included and high not, so a range has high - low items, the halves are low to mid and mid to high, and nothing is counted twice. Java finds the midpoint as low + (high - low) / 2 so that the sum of two large indices cannot overflow an int, as in Binary Search.

Each language has a sort built in, and in real code you should use it. Python's sorted and list.sort are stable. Java's Arrays.sort on an int[] is a quicksort, where stability means nothing because equal integers cannot be told apart, and on an array of objects it is a stable merge-based sort. TypeScript's sort is stable, but without a comparator it compares items as strings: in a run under Node 24, [5, 2, 10, 1].sort() gave 1 10 2 5, and sort((a, b) => a - b) gave 1 2 5 10, which is why the listing passes one. Choosing a Sorting Algorithm, a later topic, covers what each built-in runs.

← → move through sections and cards