Merge Sort

Introduction

Merge Sort is a divide-and-conquer sorting algorithm that splits an array in half, recursively sorts each half, then merges the two sorted halves back together. It’s like sorting a deck of cards by splitting it into smaller and smaller piles until each pile has one card, then merging piles together in order.

Unlike Quick Sort, which can degrade to O(n²) with bad pivot choices, Merge Sort guarantees O(n log n) in every case. The tradeoff is that it needs O(n) extra space. You’ll want to be comfortable with Recursion, Arrays, and Big-O Notation before diving in.

How Merge Sort works

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the two sorted halves into one sorted array

Visual example

[38, 27, 43, 3, 9, 82, 10]

Split:
[38, 27, 43]          [3, 9, 82, 10]
[38]  [27, 43]        [3, 9]  [82, 10]
[38]  [27] [43]       [3] [9] [82] [10]

Merge back:
[38]  [27, 43]        [3, 9]  [10, 82]
[27, 38, 43]          [3, 9, 10, 82]

[3, 9, 10, 27, 38, 43, 82]

The key insight: merging two sorted arrays into one sorted array is easy and takes O(n) time. You just compare the front elements and pick the smaller one.

Implementation

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]

import java.util.Arrays;

public class MergeSort {
    public static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;

        int mid = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));

        return merge(left, right);
    }

    static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }

        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println(Arrays.toString(mergeSort(arr)));
        // [3, 9, 10, 27, 38, 43, 82]
    }
}

In-place Merge Sort

The version above creates new arrays at every level. An in-place variant uses indices and a shared temporary buffer:

function mergeSortInPlace(arr, temp = [...arr], low = 0, high = arr.length - 1) {
  if (low >= high) return;

  const mid = Math.floor((low + high) / 2);
  mergeSortInPlace(arr, temp, low, mid);
  mergeSortInPlace(arr, temp, mid + 1, high);
  mergeInPlace(arr, temp, low, mid, high);
}

function mergeInPlace(arr, temp, low, mid, high) {
  for (let i = low; i <= high; i++) temp[i] = arr[i];

  let i = low, j = mid + 1, k = low;

  while (i <= mid && j <= high) {
    if (temp[i] <= temp[j]) {
      arr[k++] = temp[i++];
    } else {
      arr[k++] = temp[j++];
    }
  }

  while (i <= mid) arr[k++] = temp[i++];
}

const arr = [38, 27, 43, 3, 9, 82, 10];
mergeSortInPlace(arr);
console.log(arr);  // [3, 9, 10, 27, 38, 43, 82]

def merge_sort_in_place(arr, temp=None, low=0, high=None):
    if temp is None:
        temp = arr[:]
        high = len(arr) - 1
    if low >= high:
        return

    mid = (low + high) // 2
    merge_sort_in_place(arr, temp, low, mid)
    merge_sort_in_place(arr, temp, mid + 1, high)
    merge_in_place(arr, temp, low, mid, high)

def merge_in_place(arr, temp, low, mid, high):
    for i in range(low, high + 1):
        temp[i] = arr[i]

    i, j, k = low, mid + 1, low

    while i <= mid and j <= high:
        if temp[i] <= temp[j]:
            arr[k] = temp[i]
            i += 1
        else:
            arr[k] = temp[j]
            j += 1
        k += 1

    while i <= mid:
        arr[k] = temp[i]
        i += 1
        k += 1

arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort_in_place(arr)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]

public static void mergeSortInPlace(int[] arr, int[] temp, int low, int high) {
    if (low >= high) return;

    int mid = (low + high) / 2;
    mergeSortInPlace(arr, temp, low, mid);
    mergeSortInPlace(arr, temp, mid + 1, high);
    mergeInPlace(arr, temp, low, mid, high);
}

static void mergeInPlace(int[] arr, int[] temp, int low, int mid, int high) {
    for (int i = low; i <= high; i++) temp[i] = arr[i];

    int i = low, j = mid + 1, k = low;

    while (i <= mid && j <= high) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        } else {
            arr[k++] = temp[j++];
        }
    }

    while (i <= mid) arr[k++] = temp[i++];
}

This still uses O(n) extra space for the temp buffer, but it allocates it once instead of at every recursive call.

Why the merge step works

The merge step is the heart of the algorithm. It works because both halves are already sorted:

Left:  [3, 27, 38]    Right: [9, 10, 43, 82]
        ^                      ^
Compare 3 vs 9 → take 3

Left:  [3, 27, 38]    Right: [9, 10, 43, 82]
           ^                   ^
Compare 27 vs 9 → take 9

Left:  [3, 27, 38]    Right: [9, 10, 43, 82]
           ^                      ^
Compare 27 vs 10 → take 10

Left:  [3, 27, 38]    Right: [9, 10, 43, 82]
           ^                          ^
Compare 27 vs 43 → take 27

...and so on → [3, 9, 10, 27, 38, 43, 82]

Each element is compared and placed exactly once, so the merge step is O(n).

Complexity analysis

Why always O(n log n)? The array is always split exactly in half (unlike Quick Sort where the split depends on the pivot). This gives exactly log n levels. Each level does O(n) work merging. So it’s always n × log n — no exceptions.

Space: O(n) for the temporary arrays used during merging, plus O(log n) for the recursion stack.

Stability

Merge Sort is stable — equal elements maintain their original relative order. This matters when sorting objects by multiple criteria:

// Sorting students by grade, then by name
// Stable sort preserves name order within same grade
const students = [
  { name: 'Alice', grade: 'B' },
  { name: 'Bob', grade: 'A' },
  { name: 'Charlie', grade: 'B' },
];

// After stable sort by grade:
// Bob (A), Alice (B), Charlie (B)
// Alice still comes before Charlie — original order preserved

The stability comes from the <= in the merge step. When elements are equal, we take from the left half first, preserving original order.

When to use Merge Sort

• You need guaranteed O(n log n) — no worst-case surprises
• You need a stable sort
• You’re sorting linked lists — Merge Sort is ideal because it doesn’t need random access
• You’re sorting external data (files too large for memory) — merge naturally works on chunks

When to use Quick Sort instead:

• Sorting arrays in memory where cache performance matters
• Space is constrained (Quick Sort is in-place)
• Average-case speed matters more than worst-case guarantees

Practice problems

1. Sort an Array (implement Merge Sort from scratch)
2. Count of Smaller Numbers After Self (modified merge sort)
3. Reverse Pairs (count inversions using merge sort)
4. Sort a Linked List
5. Merge k Sorted Lists

The merge operation itself is a fundamental building block. Once you’re comfortable with it, problems involving merging sorted sequences, counting inversions, and external sorting become much more approachable.