Merge Sort — Divide and Conquer

Introduction

In the previous posts, we explored Bubble Sort and Selection & Insertion Sort — all of which have $O(n^2)$ worst-case performance. For small datasets they work fine, but once you have thousands or millions of elements, the slowdown becomes unbearable.

Merge Sort is our first algorithm that guarantees $O(n \log n)$ performance in every case — best, average, and worst. It uses a powerful strategy called Divide and Conquer:

1. Divide the problem into smaller sub-problems.
2. Conquer each sub-problem recursively.
3. Combine the solutions of the sub-problems into the final answer.

Think of it like organising a massive pile of exam papers with a team of helpers. You split the pile in half and hand each half to someone else. They split their halves again, and so on, until each person has just one or two papers (trivially sorted). Then everyone merges their sorted piles back together, two at a time, until the entire stack is in order.

How Merge Sort Works

1. If the array has 0 or 1 elements, it is already sorted — return it.
2. Split the array into two halves: left and right.
3. Recursively sort the left half.
4. Recursively sort the right half.
5. Merge the two sorted halves into one sorted array.

The magic happens in the merge step — combining two already-sorted arrays into one is a simple and efficient $O(n)$ operation.

Step-by-Step Walkthrough

Let’s sort [38, 27, 43, 3, 9, 82, 10].

Phase 1: Divide

                    [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]

We keep splitting until every sub-array has at most one element. A single element is sorted by definition.

Phase 2: Merge (bottom-up)

Merge [38] and [27]:

• Compare 38 vs 27 → pick 27 first, then 38.
• Result: [27, 38]

Merge [43] and [3]:

• Compare 43 vs 3 → pick 3 first, then 43.
• Result: [3, 43]

Merge [9] and [82]:

• Compare 9 vs 82 → pick 9 first, then 82.
• Result: [9, 82]

[10] stays as [10] (nothing to merge with at this level).

Merge [27, 38] and [3, 43]:

Merge [9, 82] and [10]:

Final merge [3, 27, 38, 43] and [9, 10, 82]:

Final sorted array: [3, 9, 10, 27, 38, 43, 82] ✅

Java Implementation

public class MergeSort {

    /**
     * Entry point: sorts the array using Merge Sort.
     */
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2; // avoids integer overflow vs (left+right)/2

            // Recursively sort the two halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the sorted halves
            merge(arr, left, mid, right);
        }
    }

    /**
     * Merges two sorted sub-arrays: arr[left..mid] and arr[mid+1..right].
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        // Create temporary arrays for the two halves
        int[] leftArr = new int[mid - left + 1];
        int[] rightArr = new int[right - mid];

        // Copy data into temporary arrays
        for (int i = 0; i < leftArr.length; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int j = 0; j < rightArr.length; j++) {
            rightArr[j] = arr[mid + 1 + j];
        }

        // Merge the two sorted arrays back into arr[left..right]
        int i = 0;  // pointer for leftArr
        int j = 0;  // pointer for rightArr
        int k = left; // pointer for the merged result

        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy any remaining elements from leftArr
        while (i < leftArr.length) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        // Copy any remaining elements from rightArr
        while (j < rightArr.length) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(data, 0, data.length - 1);
        // Output: [3, 9, 10, 27, 38, 43, 82]
        for (int num : data) System.out.print(num + " ");
    }
}

Key Lines Explained

Why $O(n \log n)$?

Let’s break down the two components:

1. $\log n$ levels of recursion. Each level splits the array in half. An array of 8 elements produces 3 levels ($\log_2 8 = 3$). An array of 1,024 elements produces just 10 levels.

2. $O(n)$ work at each level. Every merge step compares and copies each element exactly once. Across all the sub-arrays at one level, the total work is $n$.

So total work = $n$ work × $\log n$ levels = $O(n \log n)$.

Level 0:  [                  n elements                  ]  → n work
Level 1:  [      n/2      ]  [      n/2      ]              → n work
Level 2:  [  n/4  ][  n/4  ]  [  n/4  ][  n/4  ]            → n work
...
Level log₂n: [1][1][1]...[1][1][1]                           → n work
                                                         ─────────────
                                                         n × log₂n total

Time & Space Complexity

| Space | $O(n)$ | |:—:|:—:|

The extra space comes from the temporary arrays created during the merge step. At peak usage, we allocate arrays summing up to $n$ elements. This is the trade-off: Merge Sort is not in-place.

When to Use / When NOT to Use

Practice Problems

1. Sort an Array – LeetCode #912 — Implement Merge Sort. Compare its runtime with your earlier Bubble Sort solution.
2. Sort List – LeetCode #148 — Apply Merge Sort to a Linked List in $O(n \log n)$ time and $O(1)$ extra space.
3. Merge Sorted Array – LeetCode #88 — Practice the merge step in isolation.

What’s Next?

Merge Sort gives us guaranteed $O(n \log n)$, but at the cost of $O(n)$ extra space. Is there a way to get $O(n \log n)$ average performance in-place? Yes — meet Quick Sort — The Versatile Performer.