Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Divide the array into two halves at the midpoint.
- Recursively apply merge sort to the left half.
- Recursively apply merge sort to the right half.
- The recursion bottoms out at sub-arrays of size one, which are trivially sorted.
- Merge the two now-sorted halves by repeatedly comparing their fronts and taking the smaller.
- Continue merging back up the recursion until the whole array is one sorted run.
Key concepts
- Divide-and-conquer
- Stable sort (the merge step takes from the left run on ties)
- Not in-place: the merge step needs O(n) auxiliary space
- Guaranteed O(n log n) in every case, unlike quicksort
When to use it
When a guaranteed O(n log n) worst case and stability matter more than auxiliary memory — for example, sorting linked lists or external (disk-based) sorting of data too large for memory.
Did you know
Merge sort was invented by John von Neumann in 1945 and is one of the earliest divide-and-conquer algorithms ever described for a computer.