Merge Sort

Merge sort is the sorting algorithm that refuses to gamble. While quicksort bets on good pivots, merge sort delivers O(n log n) performance every single time — best case, average case, worst case. It achieves this through the quintessential divide-and-conquer strategy: split the problem in half, solve both halves, and combine the results.

The Core Idea

The algorithm follows three steps:

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.

The recursion bottoms out at arrays of size 1, which are sorted by definition. All the real work happens during the merge step.

The Merge Operation

Merging two sorted arrays into one sorted array is the heart of merge sort. Picture two sorted decks of cards face up. You repeatedly compare the top cards and place the smaller one into the output pile.

The two-pointer technique drives this:

• Pointer i walks through the left half.
• Pointer j walks through the right half.
• Compare left[i] with right[j], append the smaller to the result, advance that pointer.
• When one side is exhausted, append everything remaining from the other side.

void merge(int[] arr, int[] temp, int left, int mid, int right) {
    // Copy both halves into temp array
    System.arraycopy(arr, left, temp, left, right - left + 1);

    int i = left;       // Pointer into left half
    int j = mid + 1;    // Pointer into right half
    int k = left;       // Pointer into merged result

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

    // Copy remaining elements from left half (right half already in place)
    while (i <= mid) {
        arr[k++] = temp[i++];
    }
    // No need to copy remaining right half — those elements are already in arr
}

Notice the <= comparison rather than <. This preserves stability: when two elements are equal, the one from the left half goes first, maintaining their original relative order.

Top-Down Merge Sort (Recursive)

The classic recursive implementation divides the array top-down:

void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];   // Allocate once, reuse
    mergeSort(arr, temp, 0, arr.length - 1);
}

void mergeSort(int[] arr, int[] temp, int left, int right) {
    if (left >= right) return;          // Base case: single element

    int mid = left + (right - left) / 2;    // Avoid overflow
    mergeSort(arr, temp, left, mid);        // Sort left half
    mergeSort(arr, temp, mid + 1, right);   // Sort right half
    merge(arr, temp, left, mid, right);     // Merge sorted halves
}

Key implementation detail: allocate the temporary array once at the top level and pass it through the recursion. Creating a new array at every merge call wastes memory and slows things down with garbage collection pressure.

Recursion Tree Visualization

For an array of 8 elements, the recursion tree looks like this:

Level 0:  [8 elements]              → 1 merge of size 8
Level 1:  [4] [4]                   → 2 merges of size 4
Level 2:  [2] [2] [2] [2]          → 4 merges of size 2
Level 3:  [1][1][1][1][1][1][1][1] → base cases

Each level does O(n) total work (every element participates in one merge at each level), and there are log₂(n) levels. That gives us O(n log n) total work.

Bottom-Up Merge Sort (Iterative)

Bottom-up merge sort skips the recursion entirely. Instead of splitting top-down, it builds up from the bottom:

1. Start with subarrays of size 1 (already sorted).
2. Merge adjacent pairs into sorted subarrays of size 2.
3. Merge adjacent pairs into sorted subarrays of size 4.
4. Double the subarray size each pass until the entire array is sorted.

void mergeSortBottomUp(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];

    for (int size = 1; size < n; size *= 2) {          // Subarray size doubles
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = Math.min(left + 2 * size - 1, n - 1);
            merge(arr, temp, left, mid, right);
        }
    }
}

This version avoids recursion overhead (no call stack frames) and performs the exact same merges. The outer loop runs log₂(n) times, and each iteration merges all elements once — giving the same O(n log n) time.

Bottom-up merge sort is particularly useful for linked lists and external sorting scenarios where you process data in sequential passes.

Analysis

Time Complexity

The recurrence relation captures merge sort’s behavior:

$$T(n) = 2T(n/2) + O(n)$$

• 2T(n/2): Two recursive calls on halves of size n/2.
• O(n): The merge step scans all n elements.

By the Master Theorem (Case 2: a = 2, b = 2, f(n) = n, so log_b(a) = 1 = c), this resolves to:

$$T(n) = O(n \log n)$$

This holds for all cases. Unlike quicksort, merge sort always splits the array evenly — there’s no dependence on input order or element distribution. Best case, average case, worst case: all O(n log n).

Space Complexity

Merge sort requires O(n) additional space for the temporary array used during merging. The recursion stack adds O(log n), but the dominant cost is the temporary array.

This is merge sort’s primary weakness compared to quicksort and heap sort: it is not in-place.

Stability

Merge sort is stable. During the merge step, when two elements are equal, the element from the left subarray is placed first. Since the left subarray precedes the right subarray in the original array, equal elements maintain their relative positions throughout the sort.

This stability is why Java’s Arrays.sort() uses a merge sort variant (TimSort) for objects — preserving the relative order of equal elements matters when sorting by multiple criteria.

Optimization: Small Subarray Cutoff

Recursion has overhead: function calls, stack frames, and the merge setup. For small subarrays (fewer than 16 elements), insertion sort runs faster due to lower constant factors and better cache behavior.

void mergeSort(int[] arr, int[] temp, int left, int right) {
    if (right - left < 16) {
        insertionSort(arr, left, right);    // Switch to insertion sort
        return;
    }

    int mid = left + (right - left) / 2;
    mergeSort(arr, temp, left, mid);
    mergeSort(arr, temp, mid + 1, right);
    merge(arr, temp, left, mid, right);
}

TimSort, Java’s built-in sort for objects, uses this exact optimization with a minimum run size of 32.

Applications

Counting Inversions

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Counting inversions measures how “unsorted” an array is — a fully sorted array has 0 inversions, a reverse-sorted array has n(n-1)/2.

The brute-force approach checks all pairs: O(n²). Merge sort counts inversions in O(n log n) by tracking cross-inversions during the merge step.

When an element from the right half is placed before remaining elements of the left half, every remaining left element forms an inversion with it:

long countInversions(int[] arr, int[] temp, int left, int right) {
    if (left >= right) return 0;

    int mid = left + (right - left) / 2;
    long inversions = 0;

    inversions += countInversions(arr, temp, left, mid);
    inversions += countInversions(arr, temp, mid + 1, right);
    inversions += mergeAndCount(arr, temp, left, mid, right);

    return inversions;
}

long mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
    System.arraycopy(arr, left, temp, left, right - left + 1);

    int i = left, j = mid + 1, k = left;
    long inversions = 0;

    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) {
            arr[k++] = temp[i++];
        } else {
            inversions += (mid - i + 1);    // All remaining left elements are inversions
            arr[k++] = temp[j++];
        }
    }

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

When temp[j] < temp[i], every element from index i through mid in the left half is greater than temp[j], producing (mid - i + 1) inversions in one step.

External Sorting

When data doesn’t fit in memory — think sorting a 100 GB file on a machine with 4 GB of RAM — merge sort shines. The strategy:

1. Read chunks that fit in memory, sort each chunk, write sorted chunks (called “runs”) to disk.
2. Merge runs using a multi-way merge: read small buffers from each run, merge, write output.
3. Repeat until one sorted run remains.

Merge sort is ideal here because it accesses data sequentially (no random access needed) and the merge operation naturally works with streams of data arriving in order.

Linked List Sorting

Merge sort is the preferred algorithm for sorting linked lists:

• Finding the middle uses the slow/fast pointer technique: O(n).
• Merging two sorted linked lists requires no extra space — you re-link existing nodes.
• No random access penalty (unlike quicksort’s partitioning).

This gives O(n log n) time with O(log n) space (recursion stack only), compared to O(n) extra space for arrays.

Merge Sort vs. Quicksort

Property	Merge Sort	Quicksort
Worst case	O(n log n)	O(n²)
Average case	O(n log n)	O(n log n)
Space	O(n)	O(log n)
Stable	Yes	No
Cache performance	Moderate	Excellent
In-place	No	Yes

Quicksort wins in practice for arrays because of superior cache locality — it works on contiguous memory, while merge sort bounces between the main array and a temporary array.

Java reflects this trade-off:

• Arrays.sort(Object[]) → TimSort (merge sort variant): stability matters for objects.
• Arrays.sort(int[]) → Dual-Pivot Quicksort: stability doesn’t matter for primitives, and cache performance wins.

Interviewer Tips

• Start with merge: when asked to implement merge sort, write the merge method first. It’s the core operation, and interviewers want to see you handle the two-pointer merging correctly.
• Stability matters: if the problem requires stable sorting (sorting by multiple keys, preserving original order of ties), merge sort is your answer.
• Inversion counting appears frequently in interviews. Recognize the pattern: “count pairs where order is reversed” → modify merge sort.
• Space trade-off: know that merge sort’s O(n) space is its main disadvantage. If asked “can you sort in-place with O(n log n) guarantee?” → heap sort, not merge sort.
• Linked list sorting: if asked to sort a linked list in O(n log n), reach for merge sort immediately. Quicksort and heap sort both need random access.