Merge Sort: Divide, Conquer, and Combine

Merge sort is a classic divide-and-conquer algorithm that recursively splits an array into halves, sorts each half, and then merges the sorted halves back together. Its predictable performance and stability make it a favorite for handling large datasets. Explore the pseudocode and step-by-step animation below to see how each merge weaves the sorted list into existence.

Pseudocode

  1. function mergeSort(list, start, end):
  2.     if start ≥ end: return
  3.     mid ← ⌊(start + end) / 2⌋
  4.     mergeSort(list, start, mid)
  5.     mergeSort(list, mid + 1, end)
  6.     merge(list, start, mid, end)
  7. function merge(list, start, mid, end):
  8.     left ← list[start..mid]
  9.     right ← list[mid + 1..end]
  10.     i ← j ← 0
  11.     for k from start to end:
  12.         if j = |right| or (i < |left| and left[i] ≤ right[j]):
  13.             list[k] ← left[i]; i ← i + 1
  14.         else:
  15.             list[k] ← right[j]; j ← j + 1

Visualization

Left Stream

Awaiting split…

Right Stream

Awaiting split…

Input Stream Key

  • Values from the left slice of the merge.
  • Values from the right slice of the merge.
  • Dimmed bars show values already consumed.
  • Raised bars highlight the current comparison.

Algorithm Variables

start —
mid —
end —
i —
j —
k —
left slice —
right slice —
left[i] —
right[j] —