Merge Sort — The Divide and Conquer Approach

How Merge Sort Works

Merge Sort is a classic divide-and-conquer algorithm that achieves O(n log n) time complexity in all cases — best, average, and worst. It works by recursively dividing the array into halves, sorting each half, and then merging the sorted halves back together.

The Three Steps

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the two sorted halves into one sorted array

function mergeSort(arr, left, right):
  if left >= right: return
  mid = (left + right) / 2
  mergeSort(arr, left, mid)
  mergeSort(arr, mid + 1, right)
  merge(arr, left, mid, right)

The Merge Procedure

The merge step is the core of the algorithm. It takes two sorted subarrays and combines them into one sorted array by comparing elements from each subarray one at a time:

function merge(arr, left, mid, right):
  create temp arrays L = arr[left..mid], R = arr[mid+1..right]
  i = 0, j = 0, k = left
  while i < len(L) and j < len(R):
    if L[i] <= R[j]:
      arr[k] = L[i]; i++
    else:
      arr[k] = R[j]; j++
    k++
  copy remaining elements

Recursion Tree

For an array of 8 elements, the recursion tree has 3 levels (log₂ 8 = 3). At each level, all n elements are processed during merging, giving total work of n * log n.

Guaranteed O(n log n)

Unlike Quick Sort, Merge Sort's performance does not depend on the input order. The division is always into exact halves (not dependent on pivot selection), so the recursion depth is always log n and each level does O(n) work.

Trade-off: Space

The main disadvantage of Merge Sort is its O(n) extra space requirement for the temporary arrays used during merging. This makes it less suitable for memory-constrained environments.