Merge Sort

Intuition

Imagine two teachers each holding a stack of exam papers already sorted by roll number, and you need one combined sorted stack. You do not shuffle everything and start over. You look at the top paper of each stack, take whichever has the smaller roll number, and repeat. Each paper is touched once, so merging is fast and simple.

Merge sort exploits that observation. Merging two sorted lists is easy, so it reduces the hard problem (sort everything) to that easy one by splitting the array until every piece has one element. A single element is trivially sorted. Then it merges pairs of pieces back together, level by level, until one sorted array remains. This is the canonical divide and conquer algorithm: split, solve the halves, combine.

How it works step by step

1. If the range has zero or one element, it is already sorted: return.
2. Find the midpoint mid = lo + (hi - lo) / 2 and split into [lo, mid] and [mid + 1, hi].
3. Recursively merge sort the left half.
4. Recursively merge sort the right half.
5. Merge: walk two indices i (left) and j (right) and repeatedly copy the smaller front element into the output. On a tie, take from the left half so equal elements keep their original order.
6. When one half runs out, copy whatever remains of the other half.

Dry run

Input [38, 27, 43, 3, 9, 82, 10, 19]. Splitting happens on the way down the recursion; merging happens on the way back up.

Notice that there are log2(8) = 3 levels of merging, and each level touches all 8 elements once. That picture, 3 levels times 8 elements, is the whole complexity proof in miniature.

Code

The Java version sorts in place using one shared buffer allocated up front, which avoids creating new arrays at every level. It also skips the merge when the two halves are already in order, a cheap check that makes sorted input run in linear time.

import java.util.Arrays;

public class MergeSort {
    public static void sort(int[] a) {
        if (a.length < 2) return;
        int[] buf = new int[a.length];
        sort(a, buf, 0, a.length - 1);
    }

    private static void sort(int[] a, int[] buf, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, buf, lo, mid);
        sort(a, buf, mid + 1, hi);
        if (a[mid] <= a[mid + 1]) return; // halves already in order
        merge(a, buf, lo, mid, hi);
    }

    private static void merge(int[] a, int[] buf, int lo, int mid, int hi) {
        System.arraycopy(a, lo, buf, lo, hi - lo + 1);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) {
            // <= keeps equal keys in original order (stability)
            a[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
        }
        while (i <= mid) a[k++] = buf[i++];
        // leftover right-half items are already in their final slots
    }

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

def merge_sort(a):
    """Returns a new sorted list; the input is not modified."""
    if len(a) <= 1:
        return a[:]
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))


def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # <= keeps the sort stable
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


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

Time and space complexity

The recurrence is T(n) = 2T(n/2) + O(n): two half-size subproblems plus a linear merge. The recursion tree has log n levels and each level does O(n) total work, giving O(n log n) regardless of how the input is arranged. The price is the auxiliary buffer; for arrays, merge sort is not in place. On a linked list, the merge only rewires pointers, so the extra space drops to the recursion stack.

Edge cases

• Empty array or a single element: return immediately without allocating.
• Already sorted input: with the a[mid] <= a[mid + 1] check, every merge is skipped.
• Reverse sorted input: still O(n log n); merge sort has no bad inputs.
• Many duplicates: correct and stable as long as ties take from the left half.
• Odd lengths: the left half gets the extra element with this midpoint; that is fine as long as both recursive ranges are non-empty.

Common mistakes

• Using `<` instead of `<=` in the merge. The output is still sorted, but equal elements can swap order, so the sort is no longer stable. That matters when sorting records by one key after another.
• Forgetting to copy the leftovers. After the main loop, one half still has elements. Dropping them loses data.
• Wrong split bounds. Splitting into [lo, mid - 1] and [mid, hi] with a floor mid can create an empty left half and infinite recursion on two-element ranges.
• Allocating a new array in every merge call. It works, but the constant factor and garbage collection cost are large. Allocate one buffer once.
• Slicing in a loop in Python and calling it O(n log n) space. Slices copy; that is fine for clarity, but know that the simple version allocates O(n log n) memory in total over its lifetime, even though only O(n) is live at once.

Variations and when to use it

Bottom-up merge sort skips recursion: merge runs of width 1, then 2, then 4, and so on. Linked-list merge sort finds the middle with slow and fast pointers and merges by relinking nodes, which makes it the standard answer for sorting a list in O(n log n). External merge sort sorts chunks that fit in memory, writes them to disk, and then does a k-way merge with a heap. TimSort, used by Python and by Java for objects, is a merge sort that detects existing runs and uses insertion sort on short ones.

Choose merge sort when you need a guaranteed worst case, when stability matters, or when the data lives in a linked list or on disk. If you are sorting a primitive array in memory and do not care about stability, quick sort is usually faster in practice, and heap sort gives O(n log n) with O(1) extra space. The merge step itself is also a pattern: counting inversions, counting smaller elements to the right, and merging k sorted lists all piggyback on it.

Related LeetCode problems

• #912 Sort an Array — implement merge sort directly; it passes where naive quick sort can time out on adversarial tests.
• #88 Merge Sorted Array — the merge step alone, done from the back to stay in place.
• #21 Merge Two Sorted Lists — the merge step on linked lists, rewiring next pointers.
• #148 Sort List — full merge sort on a linked list, splitting with slow and fast pointers.
• #23 Merge k Sorted Lists — merge lists pairwise (divide and conquer) or with a min-heap.
• #315 Count of Smaller Numbers After Self — count how many right-half elements jump ahead of each left element during merges.
• #493 Reverse Pairs — before each merge, count cross-half pairs with a two-pointer sweep.

FAQ