Chapter 18 of 65

Merge Sort

Imagine a teacher has to arrange 1,000 exam papers in order of roll number. Doing it alone, one paper at a time, would take forever.

So she splits the pile in half and gives each half to an assistant. Each assistant splits their pile again and passes it on, until everyone has just one paper. One paper is already "sorted".

Then the piles come back up. Two people combine their sorted piles into one sorted pile, then two bigger piles are combined, and so on, until the full stack is in order.

That's Merge Sort.

Merge Sort is a divide-and-conquer sorting algorithm that splits the array into two halves, recursively sorts each half, and then merges the two sorted halves into one sorted array.

Bubble, Selection and Insertion Sort all take O(n²) time in the worst case. Merge Sort is our first algorithm that sorts in O(n log n) time, in every case.


Divide and Conquer in Three Steps

Merge Sort follows a strategy called divide and conquer. It has a whole chapter of its own later, but the idea is simple:

1. Divide   → Split the problem into smaller subproblems
2. Conquer  → Solve each subproblem (usually recursively)
3. Combine  → Join the sub-answers into the final answer

For Merge Sort, this becomes:

1. Divide   → Split the array into a left half and a right half
2. Conquer  → Sort each half using Merge Sort (recursion)
3. Combine  → Merge the two sorted halves

The recursion stops when a piece has 0 or 1 elements, because such a piece is already sorted. This is the base case you learned about in the Recursion chapter.


The Heart of Merge Sort: Merging

Before we look at the full algorithm, let's understand the most important step: merging two sorted arrays.

Suppose we have:

Left:  [3, 27, 38, 43]
Right: [9, 10, 82]

Both are already sorted. We want one sorted array.

We use two pointers, one at the start of each array. At every step, we compare the two front elements and take the smaller one.

Left (rest)    Right (rest) Compare    Result
[3,27,38,43]   [9,10,82]    3 vs 9     [3]
[27,38,43]     [9,10,82]    27 vs 9    [3, 9]
[27,38,43]     [10,82]      27 vs 10   [3, 9, 10]
[27,38,43]     [82]         27 vs 82   [3, 9, 10, 27]
[38,43]        [82]         38 vs 82   [3, 9, 10, 27, 38]
[43]           [82]         43 vs 82   [3, 9, 10, 27, 38, 43]
[]             [82]         left empty → copy the rest

Final result:

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

Every comparison places one element into the result, so merging two arrays with a total of n elements takes:

O(n) time

When one side runs out, the remaining elements on the other side are already sorted and bigger than everything placed so far, so we just copy them over.


How Merge Sort Works: Full Example

Let's sort:

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

Phase 1: Divide

Keep splitting until every piece has one element:

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

Phase 2: Merge Back Up

Now merge pairs of sorted pieces on the way back:

   [38]   [27]  [43]   [3]    [9]  [82]   [10]
      \    /      \    /        \   /       |
     [27, 38]    [3, 43]       [9, 82]    [10]
          \         /              \      /
        [3, 27, 38, 43]          [9, 10, 82]
                \                    /
              [3, 9, 10, 27, 38, 43, 82]

Notice that the real work (comparing and arranging) happens in the merge step. Splitting is just calculating a middle index.


Merge Sort in Java

Here's a complete program. It prints every merge so you can follow the recursion.

import java.util.Arrays;

class Main {

    static void mergeSort(int[] arr, int low, int high) {

        if (low >= high) {
            return; // 0 or 1 element: already sorted
        }

        int mid = low + (high - low) / 2;

        mergeSort(arr, low, mid);        // sort left half
        mergeSort(arr, mid + 1, high);   // sort right half

        merge(arr, low, mid, high);      // combine them
    }

    static void merge(int[] arr, int low, int mid, int high) {

        int[] temp = new int[high - low + 1];

        int i = low;       // pointer for left half
        int j = mid + 1;   // pointer for right half
        int k = 0;         // pointer for temp

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

        // Copy whatever is left over
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        while (j <= high) {
            temp[k++] = arr[j++];
        }

        // Copy back into the original array
        for (int t = 0; t < temp.length; t++) {
            arr[low + t] = temp[t];
        }

        System.out.println("Merged [" + low + ".." + high + "]: "
            + Arrays.toString(Arrays.copyOfRange(arr, low, high + 1)));
    }

    public static void main(String[] args) {

        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        mergeSort(arr, 0, arr.length - 1);

        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Output:

Merged [0..1]: [27, 38]
Merged [2..3]: [3, 43]
Merged [0..3]: [3, 27, 38, 43]
Merged [4..5]: [9, 82]
Merged [4..6]: [9, 10, 82]
Merged [0..6]: [3, 9, 10, 27, 38, 43, 82]
Sorted: [3, 9, 10, 27, 38, 43, 82]

The order of the merges tells you how the recursion runs: the entire left half is sorted first (indices 0..3), then the right half (4..6), and finally the two are merged.


Understanding the Code

The base case

if (low >= high) {
    return;
}

When low == high, the range has one element. When low > high, it is empty. Either way, there is nothing to sort.

Finding the middle safely

int mid = low + (high - low) / 2;

This gives the same answer as (low + high) / 2, but it can never overflow. If low and high are both close to Integer.MAX_VALUE, then low + high overflows into a negative number. This is the same safe-middle trick used in Binary Search.

The two recursive calls

mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);

The left half is low..mid and the right half is mid+1..high. Together they cover the range exactly once, with no gaps and no overlap.

The merge

The merge() method uses three pointers: i for the left half, j for the right half, and k for the temporary array. After merging, the sorted result is copied back into arr[low..high].


Time Complexity

Let's think about the recursion tree for an array of size n.

Level 0:            n                → merge work: n
Level 1:      n/2       n/2          → merge work: n
Level 2:   n/4  n/4  n/4  n/4        → merge work: n
  ...
Last level: 1  1  1  1 ... 1         → (no merging)

Two facts:

  • At every level, the pieces together contain all n elements, so merging that level costs O(n).

  • We halve the size each time, so there are about log₂ n levels.

Multiply them:

O(n) per level × O(log n) levels = O(n log n)

The same result comes from the recurrence relation:

T(n) = 2 T(n/2) + O(n)   →   T(n) = O(n log n)

Here 2 T(n/2) is sorting the two halves and O(n) is the merge.

Most importantly, Merge Sort always splits exactly in the middle, no matter what the data looks like. So:

Case

Time

Best

O(n log n)

Average

O(n log n)

Worst

O(n log n)

To see how big the difference is, compare with an O(n²) sort for one million elements:

n²        = 1,000,000 × 1,000,000 = 10¹²
n log₂ n  ≈ 1,000,000 × 20        = 2 × 10⁷

That's roughly 50,000 times less work.


Space Complexity

Merge Sort is not in-place in its standard form. The merge step needs a temporary array to hold the merged result.

Temporary array for merging → O(n)
Recursion call stack        → O(log n)

Total auxiliary space       → O(n)

In our code, each merge() creates a temporary array, but it becomes garbage as soon as the merge finishes. At any moment, the live temporary arrays never add up to more than O(n).

This extra memory is the main disadvantage of Merge Sort compared to Quick Sort and Heap Sort.


Merge Sort Is Stable

Look carefully at this line in merge():

if (arr[i] <= arr[j])

When the left and right elements are equal, we take the one from the left half first. The left half came earlier in the original array, so equal elements keep their original order.

That makes Merge Sort stable.

If you write < instead of <=, the array is still sorted, but equal elements from the right half jump ahead and stability is lost.

Stability is one reason Java's Arrays.sort() for objects (and Collections.sort()) uses TimSort, a merge-sort-based hybrid. The Java documentation guarantees that this sort is stable.


Bottom-Up (Iterative) Merge Sort

The recursive version splits first and merges on the way back. We can also skip the splitting and directly merge from the bottom:

Merge blocks of size 1 into blocks of size 2
Merge blocks of size 2 into blocks of size 4
Merge blocks of size 4 into blocks of size 8
...
import java.util.Arrays;

class Main {

    static void merge(int[] arr, int low, int mid, int high) {

        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;

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

        for (int t = 0; t < temp.length; t++) {
            arr[low + t] = temp[t];
        }
    }

    static void mergeSortBottomUp(int[] arr) {

        int n = arr.length;

        // size = length of the sorted blocks being merged
        for (int size = 1; size < n; size *= 2) {

            for (int low = 0; low < n - size; low += 2 * size) {

                int mid  = low + size - 1;
                int high = Math.min(low + 2 * size - 1, n - 1);

                merge(arr, low, mid, high);
            }

            System.out.println("Block size " + (2 * size) + ": "
                + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {

        int[] arr = {38, 27, 43, 3, 9, 82, 10};

        mergeSortBottomUp(arr);

        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Output:

Block size 2: [27, 38, 3, 43, 9, 82, 10]
Block size 4: [3, 27, 38, 43, 9, 10, 82]
Block size 8: [3, 9, 10, 27, 38, 43, 82]
Sorted: [3, 9, 10, 27, 38, 43, 82]

The condition low < n - size makes sure a right block actually exists. The Math.min handles the last block being shorter than the others (here, 10 had no partner in the first pass, and in the second pass the right block was just [10]).

The bottom-up version uses no recursion, so it has no call-stack cost, but it still needs O(n) temporary space and O(n log n) time.


Application: Counting Inversions

Recall from the Insertion Sort chapter that an inversion is a pair i < j with arr[i] > arr[j]. Counting them with two nested loops takes O(n²).

Merge Sort can count them in O(n log n) with one small addition.

During the merge, when we take an element from the right half, it is smaller than the current left element arr[i]. Since the left half is sorted, it is also smaller than every remaining left element arr[i..mid]. That's mid - i + 1 inversions in one go.

class Main {

    static long countInversions(int[] arr, int low, int high) {

        if (low >= high) {
            return 0;
        }

        int mid = low + (high - low) / 2;

        long count = 0;
        count += countInversions(arr, low, mid);
        count += countInversions(arr, mid + 1, high);
        count += mergeAndCount(arr, low, mid, high);

        return count;
    }

    static long mergeAndCount(int[] arr, int low, int mid, int high) {

        int[] temp = new int[high - low + 1];
        int i = low, j = mid + 1, k = 0;
        long count = 0;

        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                // arr[i..mid] are all greater than arr[j]
                count += (mid - i + 1);
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid)  temp[k++] = arr[i++];
        while (j <= high) temp[k++] = arr[j++];

        for (int t = 0; t < temp.length; t++) {
            arr[low + t] = temp[t];
        }

        return count;
    }

    public static void main(String[] args) {

        int[] a = {8, 4, 2, 1};
        int[] b = {3, 7, 1, 8, 2, 6, 4, 5};

        System.out.println(countInversions(a, 0, a.length - 1));
        System.out.println(countInversions(b, 0, b.length - 1));
    }
}

Output:

6
13

[8, 4, 2, 1] is fully reversed, so every one of its 4 × 3 / 2 = 6 pairs is an inversion. The second array gives 13, the same number of shifts Insertion Sort made on it.

We use long because an array of n elements can have up to n(n - 1) / 2 inversions, which overflows int for n around 66,000 and above.


Common Mistakes

1. Forgetting the leftover elements

After the main loop, one half may still have elements. Without the two "copy the rest" loops, those elements disappear.

2. Wrong split boundaries

// Wrong: infinite recursion when high = low + 1
mergeSort(arr, low, mid - 1);
mergeSort(arr, mid, high);

// Correct
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);

With low = 0 and high = 1, mid = 0, so mergeSort(arr, mid, high) calls itself with the same range forever and causes a StackOverflowError.

3. Copying back to the wrong position

The temp array starts at index 0, but the range in arr starts at low. Copy with arr[low + t] = temp[t], not arr[t] = temp[t].

4. Using < in the merge comparison

It still sorts, but the algorithm is no longer stable.

5. Overflow in the middle index

Prefer low + (high - low) / 2 over (low + high) / 2.


Advantages and Disadvantages

Advantages

Disadvantages

Guaranteed O(n log n) in every case

Needs O(n) extra memory for arrays

Stable

Slower than Insertion Sort for very small arrays

Predictable performance, no bad inputs

Not adaptive in its basic form (sorted input still costs O(n log n))

Works well for linked lists and huge files that don't fit in memory

Usually a bit slower than Quick Sort in practice for arrays

Where Merge Sort Shines

  • Linked lists: merging lists only needs pointer changes, not a temporary array, so Merge Sort is the go-to algorithm for sorting linked lists.

  • External sorting: when data is too big for RAM, we sort chunks that fit in memory, write them to disk, and then merge the sorted chunks.

  • Stable sorting of objects: sorting employees by department while keeping an earlier sort by name, for example.


Merge Sort vs Insertion Sort

Property

Insertion Sort

Merge Sort

Best case

O(n)

O(n log n)

Worst case

O(n²)

O(n log n)

Extra space

O(1)

O(n)

Stable

Yes

Yes

Best for

Small or nearly sorted data

Large data, guaranteed speed

This is exactly why TimSort combines them: insertion sort for small runs, merging for the big picture.


Interview Tips and Practice

  • Be ready to write merge() from memory. It also appears on its own in many problems.

  • Explain the O(n log n) using the "log n levels, O(n) work per level" argument.

  • Know why it is stable (<= takes from the left) and why it needs O(n) extra space.

  • Whenever a problem asks you to count pairs i < j with some ordering condition, think "modified merge sort".

Practice problems:

  • Merge Sorted Array (LeetCode 88)

  • Sort an Array (LeetCode 912)

  • Count Inversions (classic GeeksforGeeks problem)

  • Reverse Pairs (LeetCode 493)

  • Count of Smaller Numbers After Self (LeetCode 315)

  • Sort List (LeetCode 148), after you learn Linked Lists


The Main Idea

Merge Sort splits the array in half, sorts each half recursively, and merges the two sorted halves.

Split in half
     ↓
Sort left half (recursively)
     ↓
Sort right half (recursively)
     ↓
Merge the two sorted halves

Its key facts:

Time   → O(n log n) in best, average and worst case
Space  → O(n) extra
Stable → Yes
In-place → No (standard array version)

Merge Sort trades extra memory for a guaranteed O(n log n) running time and stability, and its merge step is one of the most reused ideas in DSA.

In the next chapter, we'll learn Quick Sort, which also uses divide and conquer but does its real work before the recursive calls and sorts in place.