☕ DSA Java Articles

Topics › Sorting › Sorting-II

Merge Sorting

Medium TUF ID 945 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array arr of n integers. Sort it in non-decreasing order using merge sort: split the array into halves, sort each half recursively, then merge the two sorted halves into one sorted array.

Constraints: 1 ≤ n ≤ 10^5, values fit in a 32-bit signed integer. Duplicates and negative numbers are allowed. With n this large, the quadratic sorts are out; merge sort’s O(n log n) is about 1.7 × 10^6 steps.

Example 1

arr = [3, 1, 2, 4, 1, 5, 2, 6, 4]
answer = [1, 1, 2, 2, 3, 4, 4, 5, 6]  // duplicates are kept

Example 2

arr = [4, 2, 1, 3]
answer = [1, 2, 3, 4]                 // halves [4, 2] and [1, 3] become [2, 4] and [1, 3], then merge

Approach 1: Divide, copy, merge

Intuition. Merge sort is built on one observation: merging two sorted arrays is easy and linear. Put a finger on the front of each; the smaller of the two fingered elements is the smallest of everything that is left, so output it and advance that finger. Each step consumes one element, so merging a and b costs |a| + |b| steps.

Given a linear merge, sorting becomes divide and conquer: cut the array in half, sort both halves (recursively, by the same procedure), and merge. The recursion stops when a piece has fewer than two elements, which is trivially sorted. The most direct implementation copies the halves into their own arrays, sorts those, and merges them back into the original.

Algorithm.

  1. If arr has fewer than two elements, return.
  2. Copy arr[0..mid-1] to left and arr[mid..n-1] to right, with mid = n / 2.
  3. Recursively sort left and right.
  4. Merge: while both have elements, copy the smaller front element into arr (taking from left on ties); then copy whatever remains of either half.
static void mergeSortCopying(int[] arr) {
    if (arr.length < 2) return;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    mergeSortCopying(left);
    mergeSortCopying(right);
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) arr[k++] = left[i++]; else arr[k++] = right[j++];
    }
    while (i < left.length) arr[k++] = left[i++];
    while (j < right.length) arr[k++] = right[j++];
}

Complexity. Time O(n log n): the recursion has log n levels and the merges on each level touch every element once, so T(n) = 2T(n/2) + O(n). Space O(n) live memory at any moment (the halves along one root-to-leaf path sum to less than 2n) plus O(log n) recursion stack, but a total of O(n log n) ints are allocated over the run, which is what makes this version slower than the next one.

Approach 2: Index ranges and one shared buffer

Intuition. Copying halves is convenient but unnecessary. The recursion can work on index ranges [lo, hi] of the same array; the only place that needs scratch space is the merge, and one buffer of size n, allocated once and shared by every call, is enough. The merge writes the merged run into tmp[lo..hi] and copies it back. Nothing else changes.

Algorithm.

  1. mergeSort(arr) allocates tmp and calls the recursive version on [0, n - 1].
  2. mergeSort(arr, tmp, lo, hi): if lo >= hi return; compute mid, recurse on [lo, mid] and [mid + 1, hi], then merge.
  3. merge: walk i over [lo, mid] and j over [mid + 1, hi], writing the smaller element to tmp[k]; copy leftovers; copy tmp[lo..hi] back into arr.
static void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int[] tmp = new int[arr.length];
    mergeSort(arr, tmp, 0, arr.length - 1);
}

static void mergeSort(int[] arr, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(arr, tmp, lo, mid);
    mergeSort(arr, tmp, mid + 1, hi);
    merge(arr, tmp, lo, mid, hi);
}

static void merge(int[] arr, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;         // left run arr[lo..mid], right run arr[mid+1..hi]
    while (i <= mid && j <= hi) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++]; else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= hi) tmp[k++] = arr[j++];
    for (k = lo; k <= hi; k++) arr[k] = tmp[k];
}

Dry run of the final merge in Example 2, with left run [2, 4] and right run [1, 3]:

arr[i] arr[j] arr[i] <= arr[j]? written to tmp i j
2 1 no 1 0 1
2 3 yes 2 1 1
4 3 no 3 1 2 (right exhausted)
4 – left leftovers 4 2 2

tmp[0..3] = [1, 2, 3, 4] is copied back. The recursion tree for [4, 2, 1, 3] is: [4, 2] → [4], [2] → [2, 4]; [1, 3] → [1], [3] → [1, 3]; then this merge.

Complexity. Time O(n log n) as before, with a much smaller constant because no arrays are created during the recursion. Space O(n) for tmp plus O(log n) stack frames.

The tie rule arr[i] <= arr[j] is what makes merge sort stable: when both runs hold equal elements, the one from the left run (which was earlier in the original array) is written first. Change it to < and equal elements from the right run would jump ahead.

Approach 3: Bottom-up, no recursion

Intuition. Look at the recursion tree from the leaves up. At the bottom every element is a run of width 1. The level above merges adjacent runs into width 2, the next into width 4, and so on. Nothing forces us to arrive there by recursion: we can iterate the widths directly, 1, 2, 4, ..., and for each width merge the pairs of adjacent runs left to right. The same merge routine does the work. This removes the call stack entirely and is the form used for sorting linked lists and external data.

Algorithm.

  1. If n < 2 return; allocate tmp.
  2. For width = 1, 2, 4, ... while width < n:
  3. For lo = 0, 2·width, 4·width, ... while a right run exists (lo < n - width): set mid = lo + width - 1, hi = min(lo + 2·width - 1, n - 1), and merge [lo, mid] with [mid + 1, hi].
static void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    if (n < 2) return;
    int[] tmp = new int[n];
    for (int width = 1; width < n; width *= 2) {
        for (int lo = 0; lo < n - width; lo += 2 * width) {
            int mid = lo + width - 1;
            int hi = Math.min(lo + 2 * width - 1, n - 1);
            merge(arr, tmp, lo, mid, hi);
        }
    }
}

Complexity. Time O(n log n): ⌈log2 n⌉ widths, each merging every element at most once. Space O(n) for the buffer and O(1) stack.

Two details carry the correctness. The condition lo < n - width guarantees mid + 1 = lo + width ≤ n - 1, so the right run is non-empty; a leftover run with no partner is simply left alone and picked up at the next width. And hi is clamped to n - 1 because the last right run may be shorter than width when n is not a power of two. The tests include n = 12345 for exactly this reason.

Edge cases and pitfalls