mastorna.it
IT

Sorting algorithms Β· 2/7

Merge sort

Divides the array, sorts both halves and merges them linearly.

Average timeΘ(n log n) SpaceΘ(n) StableYes In placeNo

How it works

Recursion splits down to singletons. Merge repeatedly copies the smaller front item from two sorted halves.

Invariant: The buffer contains the smallest examined items in order; both remaining tails stay sorted.

Step-by-step visualization

The bar view shows comparisons and copies; the parallel tree follows the array splits and the subsequent merges.

Use 2 to 16 values. This visualizer accepts values from 0 to 999.

Split and merge tree Blue: current operation Β· green: completed merge

Comparisons
0
Writes
0
Swaps
0
Pass / level
0
active comparison pivot / key final

Pseudocode linked to the visualization

Merge sort

  1. mergeSort(A, left, right)
  2. if left β‰₯ right: return
  3. mid ← ⌊(left + right) / 2βŒ‹
  4. mergeSort(A, left, mid)
  5. mergeSort(A, mid + 1, right)
  6. merge(A, left, mid, right)

Merge

  1. merge(A, left, mid, right)
  2. L ← A[left … mid]
  3. R ← A[mid + 1 … right]
  4. i ← 0; j ← 0; B ← empty array
  5. while i < length(L) and j < length(R)
  6. if L[i] ≀ R[j]
  7. append L[i] to B; i ← i + 1
  8. else
  9. append R[j] to B; j ← j + 1
  10. append the remaining elements of L or R to B
  11. for k ← 0 to length(B) βˆ’ 1
  12. A[left + k] ← B[k]

The highlighted line corresponds to the operation described by the visualizer. Index-management details are intentionally simplified.

Complexity analysis

Best caseΘ(n log n)

Even sorted input crosses log n levels with n merge work per level, Θ(n log n).

Average caseΘ(n log n)

T(n)=2T(n/2)+Θ(n)=Θ(n log n), independent of input order.

Worst caseΘ(n log n)

The same log n levels give a Θ(n log n) guarantee.

Auxiliary spaceΘ(n)

Array merge sort uses a Θ(n) buffer and Θ(log n) stack. Taking left on ties preserves stability.

Properties at a glance

Stable

Stability concerns the relative order of elements with equal keys.

Not in place

This classification refers to the version shown on this page.

When to use it and what to avoid

A good choice when…

Strong when stability and a guarantee matter, and for linked lists or external sorting.

Common mistake

Taking from the right half on equal keys breaks stability.