Previous Topic

What Is Merge Sort?

Merge sort is a comparison-based sorting algorithm that follows a divide-and-conquer strategy. It repeatedly divides the input into smaller subproblems, solves each recursively, and then merges the results to produce a sorted sequence. It guarantees O(n log n) time in the best, average, and worst cases and is stable, preserving the relative order of equal elements.

How It Works (Divide and Conquer)

1. Divide: Split the array into two halves until subarrays have size 0 or 1.
2. Conquer: Recursively sort each half.
3. Combine: Merge the two sorted halves into one sorted array by repeatedly taking the smaller front element from each half.

Merging Procedure

The merge step walks two sorted lists in linear time and produces a new sorted list:

• Compare the current elements of the left and right lists.
• Append the smaller element to the output and advance in that list.
• When one list is exhausted, append the remainder of the other list.

Pseudocode (Top-Down)

function merge_sort(A):
  if length(A) <= 1:
    return A
  mid = length(A) // 2
  left  = merge_sort(A[0:mid])
  right = merge_sort(A[mid:])
  return merge(left, right)

function merge(L, R):
  i = 0; j = 0
  out = empty list
  while i < length(L) and j < length(R):
    if L[i] <= R[j]:      # '<=' makes it stable
      append L[i] to out; i += 1
    else:
      append R[j] to out; j += 1
  while i < length(L): append L[i] to out; i += 1
  while j < length(R): append R[j] to out; j += 1
  return out

Pseudocode (Bottom-Up, Iterative)

Bottom-up merge sort avoids recursion by merging runs of size 1, then 2, 4, 8, and so on.

function merge_sort_bottom_up(A):
  n = length(A)
  width = 1
  buffer = array of length n
  while width < n:
    for i in range(0, n, 2*width):
      left_start  = i
      left_end    = min(i + width, n)
      right_start = left_end
      right_end   = min(i + 2*width, n)
      merge_into(A, left_start, left_end, right_start, right_end, buffer)
    swap A and buffer
    width = width * 2
  return A

Worked Example

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

• Split until singletons: [38] [27] [43] [3] [9] [82] [10]
• Merge pairs: [27, 38], [3, 43], [9, 82], [10]
• Merge again: [3, 27, 38, 43], [9, 10, 82]
• Final merge: [3, 9, 10, 27, 38, 43, 82]

Complexity and Properties

• Time Complexity: O(n log n) in best, average, and worst cases.
• Space Complexity (arrays): O(n) auxiliary space for the merge buffer. Recursion stack adds O(log n).
• Space Complexity (linked lists): O(1) extra (besides recursion stack), since nodes are relinked.
• Stable: Yes (if the merge uses <= when comparing).
• Not in-place (array variant): Requires additional buffer space for merging.

Variants and Uses

• Top-down (recursive): Simple to implement and reason about.
• Bottom-up (iterative): Avoids recursion and can be cache-friendly with careful buffering.
• External merge sort: Sorts data sets larger than memory by merging sorted runs stored on disk.
• Parallel merge sort: Splits work across cores; merging can also be parallelized.
• Linked list merge sort: Attractive due to O(1) auxiliary space and easy splitting/merging.

When to Use Merge Sort

• You need predictable O(n log n) performance regardless of input order.
• You require a stable sort (e.g., multi-key sorting).
• You’re sorting linked lists or performing external sorting on very large data.

Common Pitfalls

• Forgetting to handle remainder elements during merge.
• Off-by-one errors in split and merge index ranges.
• Unnecessary allocations on each merge; prefer reusing a buffer.
• Accidentally breaking stability by using '<' instead of '<=' when merging.

Next Topic