← Sorting

Merge Sort

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

603182139425764758Auxiliary array

Step 1 of 39

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

0
Comparisons
0
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