15.3 Merge Sort Revisited

You need to sort a collection of elements efficiently while preserving the relative order of equal values.

algorithmsdivide-and-conquerrecursion

15.3 Merge Sort Revisited

Problem

You need to sort a collection of elements efficiently while preserving the relative order of equal values. The input may already be partially sorted, completely random, or adversarially arranged.

Quadratic algorithms such as selection sort, insertion sort, and bubble sort become impractical as input size grows. For an array containing one million elements, an (O(n^2)) algorithm may require trillions of comparisons, while an (O(n \log n)) algorithm remains practical.

How can divide and conquer be used to build a predictable, stable, and efficient sorting algorithm?

Solution

Use Merge Sort.

Merge sort recursively divides the input into two halves, sorts each half independently, and then merges the two sorted sequences into a single sorted result.

The algorithm consists of only three steps:

  1. Divide the array into two halves.
  2. Recursively sort both halves.
  3. Merge the sorted halves.

The power of merge sort comes from the observation that merging two already-sorted arrays can be performed in linear time.

High-Level Algorithm

Given:

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

Divide:

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

Continue recursively:

[38]
[27, 43]

[3, 9]
[82, 10]

Eventually every subproblem contains one element:

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

Single-element arrays are already sorted.

The algorithm then merges upward:

[27] + [43] → [27, 43]

[38] + [27, 43]
→ [27, 38, 43]

until the entire array becomes sorted.

Merge Operation

The merge procedure is the heart of the algorithm.

Suppose we have:

Left:
[2, 5, 8]

Right:
[1, 4, 9]

Compare front elements:

2 vs 1

Take 1.

Result:

[1]

Compare:

2 vs 4

Take 2.

Result:

[1, 2]

Continue:

[1, 2, 4, 5, 8, 9]

Each element moves exactly once during the merge.

Therefore:

$$ \text{Merge Cost} = O(n) $$

where (n) is the total number of elements being merged.

Implementation

Recursive Version

func MergeSort(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }

    mid := len(nums) / 2

    left := MergeSort(nums[:mid])
    right := MergeSort(nums[mid:])

    return Merge(left, right)
}

func Merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))

    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    result = append(result, right[j:]...)

    return result
}

The implementation closely follows the divide-and-conquer structure.

Recurrence Analysis

At each recursive call:

  • Two subproblems are created.
  • Each subproblem has size (n/2).
  • Merging costs (n).

The recurrence becomes:

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

From the previous section:

$$ n^{\log_2 2}=n $$

The merge cost matches the critical term.

Case 2 of the Master Theorem applies.

Result:

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

Recursion Tree View

Level 0:

n

Level 1:

n/2 + n/2

Level 2:

n/4 + n/4 + n/4 + n/4

Each level performs:

$$ n $$

total work.

There are:

$$ \log_2 n $$

levels.

Therefore:

$$ n+n+n+\cdots+n $$

repeated (\log n) times gives:

$$ \Theta(n\log n) $$

Stability

A sorting algorithm is stable if equal elements retain their original relative order.

Consider:

(5,A)
(3,X)
(5,B)

After sorting:

(3,X)
(5,A)
(5,B)

A stable sort preserves the order of A and B.

Merge sort achieves stability naturally.

During merging, when equal elements are encountered:

if left[i] <= right[j]

the left element is chosen first.

This preserves original ordering.

Space Complexity

Merge sort requires temporary storage.

For an array of size (n):

$$ O(n) $$

additional memory is typically allocated.

This is the primary disadvantage compared with in-place algorithms such as heapsort.

Algorithm Time Extra Space Stable
Merge Sort (O(n\log n)) (O(n)) Yes
Quick Sort (O(n\log n)) average (O(\log n)) No
Heap Sort (O(n\log n)) (O(1)) No

Bottom-Up Merge Sort

Recursion is not strictly necessary.

Start by treating every element as a sorted block of size 1:

[8] [3] [6] [1]

Merge neighboring blocks:

[3,8] [1,6]

Merge again:

[1,3,6,8]

This iterative version avoids recursion and often performs better in production systems.

External Sorting

Merge sort is especially important when data exceeds memory capacity.

Suppose:

  • 1 TB dataset
  • 32 GB RAM

The data can be divided into manageable chunks:

  1. Sort each chunk in memory.
  2. Write sorted chunks to disk.
  3. Merge the sorted files.

This technique forms the basis of external merge sort used in:

  • Database systems
  • Search engines
  • Data warehouses
  • Distributed analytics platforms

Many industrial sorting systems are fundamentally merge-sort variants.

Common Mistakes

Forgetting Remaining Elements

After one side is exhausted:

result = append(result, left[i:]...)
result = append(result, right[j:]...)

must copy remaining values.

Missing this step produces incomplete results.

Incorrect Midpoint Calculation

For very large arrays:

mid := len(nums) / 2

is safe because lengths are nonnegative.

In index-based implementations, overflow-safe midpoint formulas are often preferred.

Breaking Stability

Changing:

<=

to:

<

may alter stability.

Equal elements from the right side can leap ahead of earlier equal elements.

Excessive Allocation

Creating many temporary arrays can hurt performance.

Production implementations often reuse buffers.

Discussion

Merge sort represents one of the purest divide-and-conquer algorithms. The divide step is trivial, the conquer step consists of identical recursive calls, and the combine step performs all meaningful work. This separation makes correctness proofs straightforward and performance highly predictable.

Unlike quicksort, merge sort's running time remains (O(n \log n)) regardless of input order. There are no pathological cases that degrade performance to quadratic behavior. This predictability explains why merge sort remains the preferred choice in many database engines, file-sorting utilities, distributed systems, and standard-library implementations where worst-case guarantees and stability are more important than minimizing auxiliary memory. In the next section, we examine quicksort, a divide-and-conquer algorithm that sacrifices worst-case guarantees in exchange for exceptional practical performance and cache efficiency.