Free explainer · Video · Code · Quiz

Merge Sort

Cut the array in half, sort each half, then merge the two sorted halves in one pass. A stable top-down merge sort with one buffer shared by every merge: O(n log n) on every input, O(n) extra memory.

Difficulty: Medium
Time: O(n log n)
Space: O(n)

Take the quiz

How it works

The idea, a worked example, and the traps to avoid.

The idea

Two friends each hand you a stack of exam papers, already sorted by score. To make one sorted stack you don't need to think hard: look at the top paper of each stack, take the lower one, repeat. One pass and you're done. That's a merge.

Merge sort turns that easy job into a whole sorting algorithm. You can't merge an unsorted array, but you can cut it in half, sort each half (the same way, recursively), then merge the two sorted halves. Keep cutting and you reach pieces of one element, and a single element is already sorted. From there it's merges all the way back up.

It's divide and conquer, like quick sort, with the work in the opposite place. Quick sort does the hard part when it splits and has nothing left to do afterwards. Merge sort splits without thinking (always down the middle) and does the real work when it joins.

Walkthrough

Sort [8, 3, 5, 3, 9, 1]. There are two 3s. Call them 3a (index 1) and 3b (index 3) so we can follow them.

Split down the middle until every piece holds one value:

            [8, 3a, 5, 3b, 9, 1]
          /                      \
    [8, 3a, 5]                [3b, 9, 1]
     /      \                  /      \
   [8]    [3a, 5]           [3b]    [9, 1]
           /   \                    /   \
         [3a]  [5]                [9]   [1]

Merge back up, two sorted pieces at a time:

[3a] + [5] → [3a, 5], then [8] + [3a, 5] → [3a, 5, 8]
[9] + [1] → [1, 9], then [3b] + [1, 9] → [1, 3b, 9]

The last merge, [3a, 5, 8] with [1, 3b, 9], one step at a time:

Step	Left front	Right front	Take	Result so far
1	3a	1	1 (right)	`[1]`
2	3a	3b	3a (left: a tie goes left)	`[1, 3a]`
3	5	3b	3b (right)	`[1, 3a, 3b]`
4	5	9	5 (left)	`[1, 3a, 3b, 5]`
5	8	9	8 (left)	`[1, 3a, 3b, 5, 8]`
6	–	9	the left half is used up, 9 is already in place	`[1, 3a, 3b, 5, 8, 9]`

Step 2 is the one to remember. On a tie we take from the left half, so 3a, which started first, ends first. That one choice is what makes merge sort stable.

The choices in this code

One buffer, allocated once. A merge needs somewhere to put the two halves while it writes the result back. The top-level mergeSort allocates a single buffer the size of the array and passes it to every call. Each merge copies its range [lo, hi) into the same slots of that buffer, then merges from the buffer back into the array. The textbook version that does left = values.slice(lo, mid) inside every call works too, but it makes about n small allocations and copies, which is pure overhead.

Half-open ranges [lo, hi). lo is included and hi isn't. The halves are [lo, mid) and [mid, hi), so they meet at mid with no + 1 or - 1 to get wrong, and the size is just hi - lo. A range with fewer than two values is already sorted, so that's the base case.

The right-hand leftovers stay put. When the left half runs out first, the values still waiting on the right are already sitting in their final slots: the write position k has caught up with j. Only the left leftovers need copying, which is why there's one cleanup loop, not two.

Why it's correct

The merge keeps one promise: values[lo..k) holds the smallest k - lo values of the two halves, in sorted order. Each step takes the smaller of the two fronts. Both halves are sorted, so no value still waiting in either half can be smaller than the one just taken, and the promise holds one step further. When both halves are used up, the whole range is sorted.

The recursion ends because every split makes two strictly smaller, non-empty ranges, and ranges of size zero or one are sorted by definition. Sorted halves plus a correct merge give a sorted range, all the way up.

Complexity

Time: O(n log n), on every input. The split is always down the middle, whatever the values are, so there are about log₂ n levels of halving. At each level the merges together touch all n values once. n values times log₂ n levels: a million values take about 20 passes. Sorted, reversed, all equal or random makes no difference to the shape, so there is no bad case, unlike quick sort's O(n²).
Space: O(n). The buffer is as big as the array. The call stack only goes about log₂ n deep, which is small next to the buffer. That extra memory is the price of the guarantee. Quick sort needs only O(log n).

Stability, and why it matters

A sort is stable when values that compare equal come out in the order they went in. With plain integers you can't see the difference. With records, you can.

Say a shop's orders are already sorted by time, and you sort them again by customer. A stable sort keeps each customer's orders in time order for free. An unstable one may shuffle them. This is how "sort by price, then by rating" works in a table: sort by the second key first, then stable-sort by the first.

Merge sort is stable because of one character: the merge takes from the left half when left <= right. Write < instead and ties go right, so the array still comes out sorted, but no longer stable. No test that only checks the order of plain numbers will catch that bug.

Common bugs

< instead of <= in the merge. Still sorted, silently unstable. Test it with records that share a key.
A new array in every call. slice or new Array inside the recursion allocates and copies over and over. Allocate the buffer once and pass it down.
Mixing range styles. With inclusive ranges [lo, hi], the halves are [lo, mid] and [mid + 1, hi]. Write [lo, mid - 1] and [mid, hi] and the two-element range [0, 1] gets mid = 0 and recurses into [0, 1] forever. Half-open ranges avoid the question.
Forgetting the leftovers. When one half runs out, the rest of the other half still has to land. Here only the left half needs a loop; with a separate output array, both do.
Rebinding instead of writing (Python). values = merged inside a function changes the local name, not the caller's list. Write into values[k], or use values[:] = merged.
Overflow in (lo + hi) / 2 in Java or C++. Use lo + (hi - lo) / 2.

When to use it (and when not)

Reach for merge sort when:

You need a stable sort. Python's sorted and Java's Arrays.sort on objects use Timsort, a merge sort tuned for real data. JavaScript's Array.prototype.sort has had to be stable since ES2019, and V8 uses Timsort too. C++ has std::stable_sort.
You need a guaranteed worst case. O(n log n) no matter what the input looks like.
You're sorting a linked list. Merging two lists only relinks nodes, so it needs no buffer at all, and merge sort never needs to jump to an index. Quick sort and heap sort both do.
The data doesn't fit in memory (external sorting). Sort chunks that fit, write each one to disk as a sorted run, then merge the runs while reading each one front to back. Databases sort big tables this way.

Look elsewhere when memory is tight and stability doesn't matter: quick sort or heap sort sort in place. For a few dozen values insertion sort is faster, and Timsort uses it for small runs. In real projects, call the built-in sort.

Interview variations

Count inversions. How many pairs i < j have a[i] > a[j]? Run merge sort, and every time the merge takes a value from the right half, it jumps over every value still waiting on the left: add mid - i to the count. O(n log n) instead of checking all pairs in O(n²). With <=, equal values don't count, which is exactly right.
Merge k sorted lists. Keep a min-heap holding the front of each list. Pop the smallest, push the next value from that same list. O(N log k) for N values in total. Merging the lists in pairs, round after round, gives the same bound.
Bottom-up merge sort. Skip the recursion: merge runs of width 1 into width 2, then 2 into 4, 4 into 8, until one run covers the array. Same merge, same buffer, same O(n log n), and no call stack. It's also the natural way to sort a linked list (LeetCode "Sort List") with O(1) extra space.

Code

The same algorithm, step for step, in 4 languages.

JavaScript

// Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
// halves into one. A single scratch buffer, allocated once, holds the halves while they merge.

/**
 * Sorts `values` in ascending order, in place.
 * Stable: equal values keep the order they started in.
 *
 * @param {number[]} values the array to sort
 * @returns {void}
 */
export function mergeSort(values) {
  const buffer = new Array(values.length); // shared by every merge — never allocated again
  sortRange(values, buffer, 0, values.length);
}

/**
 * Sorts values[lo..hi) — lo included, hi excluded.
 *
 * @param {number[]} values
 * @param {number[]} buffer scratch space, at least as long as `values`
 * @param {number} lo
 * @param {number} hi
 */
function sortRange(values, buffer, lo, hi) {
  if (hi - lo < 2) return; // zero or one value: already sorted

  const mid = lo + Math.floor((hi - lo) / 2);
  sortRange(values, buffer, lo, mid); // left half:  [lo, mid)
  sortRange(values, buffer, mid, hi); // right half: [mid, hi)
  mergeHalves(values, buffer, lo, mid, hi);
}

/**
 * Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi).
 *
 * @param {number[]} values
 * @param {number[]} buffer
 * @param {number} lo
 * @param {number} mid
 * @param {number} hi
 */
function mergeHalves(values, buffer, lo, mid, hi) {
  for (let k = lo; k < hi; k++) buffer[k] = values[k]; // set both halves aside

  let i = lo; // next unused value of the left half
  let j = mid; // next unused value of the right half
  let k = lo; // next slot to fill in values

  while (i < mid && j < hi) {
    // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
    if (buffer[i] <= buffer[j]) {
      values[k++] = buffer[i++];
    } else {
      values[k++] = buffer[j++];
    }
  }
  while (i < mid) values[k++] = buffer[i++];
  // Whatever is left of the right half is already in place: k has caught up with j.
}

# Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
# halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
from typing import List


def merge_sort(values: List[int]) -> None:
    """Sort values in ascending order, in place.

    Stable: equal values keep the order they started in.
    """
    buffer = [0] * len(values)  # shared by every merge — never allocated again
    _sort_range(values, buffer, 0, len(values))


def _sort_range(values: List[int], buffer: List[int], lo: int, hi: int) -> None:
    """Sort values[lo..hi) — lo included, hi excluded."""
    if hi - lo < 2:
        return  # zero or one value: already sorted

    mid = lo + (hi - lo) // 2
    _sort_range(values, buffer, lo, mid)  # left half:  [lo, mid)
    _sort_range(values, buffer, mid, hi)  # right half: [mid, hi)
    _merge_halves(values, buffer, lo, mid, hi)


def _merge_halves(values: List[int], buffer: List[int], lo: int, mid: int, hi: int) -> None:
    """Merge the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi)."""
    for k in range(lo, hi):
        buffer[k] = values[k]  # set both halves aside

    i = lo  # next unused value of the left half
    j = mid  # next unused value of the right half
    k = lo  # next slot to fill in values

    while i < mid and j < hi:
        # <=, not <: on a tie the left value goes first, which is what makes the sort stable.
        if buffer[i] <= buffer[j]:
            values[k] = buffer[i]
            i += 1
        else:
            values[k] = buffer[j]
            j += 1
        k += 1
    while i < mid:
        values[k] = buffer[i]
        i += 1
        k += 1
    # Whatever is left of the right half is already in place: k has caught up with j.

/**
 * Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
 * halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
 */
public final class MergeSort {
    private MergeSort() {
    }

    /**
     * Sorts values in ascending order, in place.
     * Stable: equal values keep the order they started in.
     */
    public static void mergeSort(int[] values) {
        int[] buffer = new int[values.length]; // shared by every merge — never allocated again
        sortRange(values, buffer, 0, values.length);
    }

    /** Sorts values[lo..hi) — lo included, hi excluded. */
    private static void sortRange(int[] values, int[] buffer, int lo, int hi) {
        if (hi - lo < 2) {
            return; // zero or one value: already sorted
        }

        int mid = lo + (hi - lo) / 2;
        sortRange(values, buffer, lo, mid); // left half:  [lo, mid)
        sortRange(values, buffer, mid, hi); // right half: [mid, hi)
        mergeHalves(values, buffer, lo, mid, hi);
    }

    /** Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi). */
    private static void mergeHalves(int[] values, int[] buffer, int lo, int mid, int hi) {
        for (int k = lo; k < hi; k++) {
            buffer[k] = values[k]; // set both halves aside
        }

        int i = lo; // next unused value of the left half
        int j = mid; // next unused value of the right half
        int k = lo; // next slot to fill in values

        while (i < mid && j < hi) {
            // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
            if (buffer[i] <= buffer[j]) {
                values[k++] = buffer[i++];
            } else {
                values[k++] = buffer[j++];
            }
        }
        while (i < mid) {
            values[k++] = buffer[i++];
        }
        // Whatever is left of the right half is already in place: k has caught up with j.
    }
}

// Merge sort, top-down: split the range in half, sort each half, then merge the two sorted
// halves into one. A single scratch buffer, allocated once, holds the halves while they merge.
// (In real code reach for std::stable_sort — a tuned merge sort with the same guarantee.)
#include <vector>

// Merges the sorted halves values[lo..mid) and values[mid..hi) into one sorted values[lo..hi).
void mergeHalves(std::vector<int>& values, std::vector<int>& buffer, int lo, int mid, int hi) {
    for (int k = lo; k < hi; ++k) {
        buffer[k] = values[k];  // set both halves aside
    }

    int i = lo;   // next unused value of the left half
    int j = mid;  // next unused value of the right half
    int k = lo;   // next slot to fill in values

    while (i < mid && j < hi) {
        // <=, not <: on a tie the left value goes first, which is what makes the sort stable.
        if (buffer[i] <= buffer[j]) {
            values[k++] = buffer[i++];
        } else {
            values[k++] = buffer[j++];
        }
    }
    while (i < mid) {
        values[k++] = buffer[i++];
    }
    // Whatever is left of the right half is already in place: k has caught up with j.
}

// Sorts values[lo..hi) — lo included, hi excluded.
void sortRange(std::vector<int>& values, std::vector<int>& buffer, int lo, int hi) {
    if (hi - lo < 2) {
        return;  // zero or one value: already sorted
    }

    int mid = lo + (hi - lo) / 2;
    sortRange(values, buffer, lo, mid);  // left half:  [lo, mid)
    sortRange(values, buffer, mid, hi);  // right half: [mid, hi)
    mergeHalves(values, buffer, lo, mid, hi);
}

// Sorts values in ascending order, in place.
// Stable: equal values keep the order they started in.
void mergeSort(std::vector<int>& values) {
    std::vector<int> buffer(values.size());  // shared by every merge — never allocated again
    sortRange(values, buffer, 0, static_cast<int>(values.size()));
}

Ask about this algorithm

Stuck on a step? Ask for another example or why it works.

Test yourself

10 quick questions to check it stuck.

Q1 · mergeSort runs on [38, 27, 43, 3, 9, 82, 10], seven values. The code sets mid = lo + Math.floor((hi - lo) / 2). Which two halves does the first split make?

Take the quiz