Merge Sort: The Stable Splitter

I Learned Recursion Through This

When I first encountered recursion, I couldn't wrap my head around it. A function calling itself? My brain turned into spaghetti. "When does this even stop? Isn't this an infinite loop?"

Then I studied Merge Sort. That's when recursion finally clicked.

Merge Sort embodies the essence of recursion so clearly: break a big problem into smaller ones, solve the small ones, then combine the results. This is the textbook definition of Divide and Conquer.

At first I thought, "Why bother splitting? Just compare from the start!" But when I drew it out by hand, I got it. This note captures what I learned that day.

Step 1: Split Everything in Half

Merge Sort's first step is brutally simple. Cut the array in half. Then cut those halves in half. Keep going until each piece has only one element.

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

[38, 27, 43, 3, 9, 82, 10]
         |
    Start splitting
         ↓
[38, 27, 43, 3] | [9, 82, 10]
         ↓              ↓
[38, 27] | [43, 3]   [9, 82] | [10]
    ↓         ↓         ↓        ↓
[38] | [27] [43] | [3] [9] | [82] [10]

Once you're down to single elements, you can't split anymore. A one-element array is already sorted. This is the base case for recursion. This was my "aha" moment: "Oh, recursion DOES end eventually."

Step 2: Merge While Sorting - This Is The Magic

Splitting is easy. You just cut in half. The real genius of Merge Sort happens during the merge step.

When merging two sorted arrays, you compare the first element of each, take the smaller one, and put it in the result. Repeat until both arrays are empty.

Let's merge [27, 38] and [3, 43]:

Left: [27, 38]  Right: [3, 43]  Result: []

Step 1: 27 vs 3  → 3 is smaller  → [3]
        Left: [27, 38]  Right: [43]

Step 2: 27 vs 43 → 27 is smaller → [3, 27]
        Left: [38]  Right: [43]

Step 3: 38 vs 43 → 38 is smaller → [3, 27, 38]
        Left: []  Right: [43]

Step 4: Left is empty → Dump the rest of right → [3, 27, 38, 43]

I understood this as "merging two lines of people by height." You only need to compare the front person from each line, so it's O(n).

The Full Picture

Here's how [38, 27, 43, 3, 9, 82, 10] gets fully sorted:

                [38, 27, 43, 3, 9, 82, 10]
                          |
                    (Split in half)
                          ↓
              [38, 27, 43, 3] | [9, 82, 10]
                  |                   |
              (Split again)       (Split again)
                  ↓                   ↓
          [38, 27] | [43, 3]     [9, 82] | [10]
            |           |           |        |
          (Split)     (Split)     (Split)   (1 element)
            ↓           ↓           ↓        ↓
       [38] | [27]  [43] | [3]  [9] | [82]  [10]
         ↓       ↓     ↓      ↓    ↓      ↓    ↓
       (Sorted) (Sorted) ... (All are single elements, so sorted)

         Now merge while sorting (Merge phase)
                      ↑
       [27, 38]    [3, 43]    [9, 82]    [10]
            \         /            \        /
             (Merge)                (Merge)
                 ↓                     ↓
          [3, 27, 38, 43]         [9, 10, 82]
                  \                   /
                   \   (Final merge)  /
                    \                /
                           ↓
              [3, 9, 10, 27, 38, 43, 82]

Drawing this by hand made recursion click. You go down splitting, then come back up merging. It's like a stack—things pile up, then unwind.

The Code Made It Even Clearer

Here's Merge Sort in JavaScript:

function mergeSort(arr) {
  // Base case: arrays with 0 or 1 element are already sorted
  if (arr.length <= 1) {
    return arr;
  }

  // Step 1: Divide
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // Step 2: Conquer (recursively sort each half)
  const sortedLeft = mergeSort(left);
  const sortedRight = mergeSort(right);

  // Step 3: Merge
  return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
  const result = [];
  let i = 0; // left index
  let j = 0; // right index

  // Compare elements from both arrays and pick the smaller one
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // Dump any remaining elements
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

// Test
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

I stepped through this with a debugger to watch arrays split and merge. That's when recursion truly made sense.

Time Complexity: Always O(n log n)

The defining feature of Merge Sort is it's always O(n log n). Worst case, best case, average case—doesn't matter. Always O(n log n).

Why?

1. Number of splits: Cutting an array in half repeatedly takes log n steps. For 8 elements, you split 3 times (2³ = 8). For 16 elements, 4 times (2⁴ = 16).
2. Merging cost per level: At each level, you touch every element once, so O(n).
3. Total: log n levels × O(n) per level = O(n log n)

This is why Merge Sort is the "reliable student." Quick Sort can degrade to O(n²) in the worst case (like already-sorted arrays), but Merge Sort never surprises you. It's always consistent.

Space Complexity: Uses O(n) Extra Memory

But Merge Sort has a clear downside: it uses O(n) additional memory.

Look at the merge() function. It creates a result array the same size as the input. You need a temporary array as big as the original.

Quick Sort sorts in-place (O(log n) stack space), but Merge Sort can't do that.

I understood this as "needing an extra box to reorganize your stuff." To merge items from two boxes by size, you need a third empty box as a workspace.

This can be a dealbreaker in memory-constrained environments like embedded systems or mobile devices.

Stability: Original Order Is Preserved

Merge Sort is a stable sort. When elements have equal values, their original order is maintained.

For example, with [3a, 1, 3b, 2] (where 3a and 3b have the same value but different original positions):

• Stable sort: [1, 2, 3a, 3b] (3a stays before 3b)
• Unstable sort: [1, 2, 3b, 3a] (order might flip)

Why does this matter? When you sort by multiple criteria, order doesn't get scrambled. Say you sort students by name first, then by grade. Students with the same grade should still be in name order.

Merge Sort is stable because in the merge() function, when left[i] === right[j], we take from the left first, preserving order.

Quick Sort vs Merge Sort: Total Opposites

I fully understood Merge Sort by comparing it to Quick Sort. Both use divide and conquer, but they're polar opposites:

Feature	Quick Sort	Merge Sort
How it splits	Logical (pivot-based partitioning)	Physical (blindly cut in half)
When it sorts	While splitting	While merging
Time complexity	Avg O(n log n), worst O(n²)	Always O(n log n)
Space complexity	O(log n) (stack only)	O(n) (extra array)
Stability	Unstable	Stable
Personality	Gambler (fast but risky)	Model student (slow but guaranteed)

I summarized it like this:

• Quick Sort: "Pick a good pivot and finish fast" (aggressive)
• Merge Sort: "Split everything in half and merge carefully" (defensive)

Real-World Usage

Merge Sort is heavily used in practice, especially for external sorting.

1. External Sorting

What if you need to sort data larger than memory? Say you have a 100GB file but only 4GB of RAM:

1. Split the file into 4GB chunks, load each into memory, sort it, save to disk
2. Merge the sorted chunks using merge sort logic

Since disk I/O is expensive, Merge Sort's sequential access pattern beats Quick Sort's random access.

2. Timsort (Python, Java)

Python's sorted() and Java's Arrays.sort() use Timsort, a hybrid of merge sort and insertion sort:

• Small runs: use insertion sort (fast for small data)
• Large runs: use merge sort (stable and predictable)

Merge Sort's stability and guaranteed performance make it ideal for production use.

3. Sorting Linked Lists

For linked lists, Merge Sort is superior. Quick Sort needs random access, which costs O(n) in a linked list. Merge Sort only needs sequential access, so it works efficiently with linked lists.

Bottom-Up Merge Sort: No Recursion Needed

You don't have to use recursion. You can implement Merge Sort iteratively. This is called the bottom-up approach:

function mergeSortBottomUp(arr) {
  const n = arr.length;
  let result = [...arr]; // Copy

  // size: size of subarrays to merge (1, 2, 4, 8, ...)
  for (let size = 1; size < n; size *= 2) {
    for (let start = 0; start < n; start += size * 2) {
      const mid = Math.min(start + size, n);
      const end = Math.min(start + size * 2, n);

      // Merge [start, mid) and [mid, end)
      const left = result.slice(start, mid);
      const right = result.slice(mid, end);
      const merged = merge(left, right);

      // Copy merged result back
      for (let i = 0; i < merged.length; i++) {
        result[start + i] = merged[i];
      }
    }
  }

  return result;
}

This avoids recursive call stack overhead, so no risk of stack overflow. Useful for very large datasets.

Closing Thoughts

Merge Sort taught me recursion. The idea of "break big problems into small ones, solve the small ones, combine the answers" finally clicked when I drew it out by hand.

When deciding whether to use it, I settled on this framework:

Choose Merge Sort when:

• Stability matters (preserving order of equal elements)
• You need guaranteed O(n log n) even in the worst case
• Sequential access is preferred (linked lists, external sort)
• Memory is plentiful

Choose Quick Sort when:

• You want the fastest average performance
• Memory is tight (in-place sorting)
• Stability doesn't matter

In the end, Merge Sort is the "slow but sure model student," while Quick Sort is the "fast but risky gambler." Comparing these two algorithms gave me a deeper appreciation for the different flavors of divide and conquer.

And I'll never forget that Merge Sort was the algorithm that made recursion make sense.