Merge Sort

sorting · O(n log n) avg

5

Configure inputs and press Visualize to begin.

64
34
25
12
22
11
90
45
Default
Comparing
Swap
Pivot
Sorted
Found
Pseudocode & Implementations
2 approaches

Recursively split, sort halves, then merge. Classic divide-and-conquer.

MERGE-SORT(A, lo, hi):
  IF lo >= hi: RETURN
  mid = (lo + hi) / 2
  MERGE-SORT(A, lo, mid)
  MERGE-SORT(A, mid+1, hi)
  MERGE(A, lo, mid, hi)

MERGE(A, lo, mid, hi):
  L = A[lo..mid],  R = A[mid+1..hi]
  i = j = 0,  k = lo
  WHILE i < |L| AND j < |R|:
    IF L[i] <= R[j]: A[k++] = L[i++]
    ELSE:            A[k++] = R[j++]
  COPY remaining L or R into A
Complexity Analysis

Time Complexity

Best Case
LinearithmicO(n log n)
Average
LinearithmicO(n log n)
Worst Case
LinearithmicO(n log n)
Space (aux)
LinearO(n)
StableExtra spacedivide-conquerstableguaranteed
About

Divide-and-conquer: recursively splits the array in half, sorts each half, then merges. Guarantees O(n log n) in all cases.

Key Insight

Consistent performance regardless of input. Preferred for linked lists and external sorting.

Use Cases

Linked listsExternal sortingStable sort requirementParallel sorting