Merge sort
Splits the list in half, sorts each half, then merges the two sorted halves into one sorted list.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- yes
- no
Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
Worst case: the growth on the hardest input. Useful when speed must never drop.
Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
Stable: two equal values keep their original order. Matters when sorting by one field of a record.
In place: sorts inside the list itself, with no second list.
- comparing
- moving
- in final place
Try this: Pick a list with few unique values. When two values are equal, the one from the left half is taken first, so equal values keep their order.
How it works
Keep splitting the list until each piece has one value, which is already sorted. Then merge the pieces back in pairs: compare the first values of both pieces and take the smaller one, again and again. The raised row in the animation is the extra space used while merging.
When it is a good choice
When you need speed that stays good even in the worst case, and equal values must keep their order. Python and Java both use a version of merge sort. Its downside is the extra memory it needs.