Merge Sort

A divide-and-conquer algorithm that splits, sorts, and merges subarrays.

Step 1 of 39

Starting Merge Sort. Divide the array in half, sort each half, then merge.

Comparisons

Moves

▶Algorithm

MergeSort(arr, lo, hi):
if lo ≥ hi: return
mid = (lo + hi) / 2
MergeSort(arr, lo, mid)
MergeSort(arr, mid+1, hi)
copy arr[lo..hi] to aux
merge aux back into arr[lo..hi]
// sorted

Legend

In aux (merging)

Written back

Sorted

Unsorted

The auxiliary array below shows the temporary buffer used during merging. Elements are copied in, compared, and written back to the main array.

1 / 39Speed