Sorting Algorithms
linearithmic · stable · needs scratch space

Watch <merge sort> run.

Split until the pieces are single values, then merge them back in order. The blue band is the slice being worked on; the strip underneath is the scratch space it has to copy into — the memory the other sorts on this site never needed.

What it costs

Best case
O(n log n)The recursion splits log₂n deep regardless of the input, and every level touches all n values. Sorted input saves a little on comparisons, nothing on structure.
Average
O(n log n)Between n·log₂n⁄2 and n·log₂n comparisons. Try every preset — the count barely moves.
Worst case
O(n log n)No input degrades it. That guarantee is the reason it is used where latency has to be predictable.
Extra memory
O(n)The one real cost. Each merge copies both halves out before writing back, so the scratch space grows with the slice. This is the trade the quadratic sorts refuse to make.
Stable
YesThe merge takes from the left run when the two values are equal — that is what <= is doing on the compare line. Change it to < and equal values swap order.
Used in practice
YesJava's Arrays.sort on objects and Python's sorted both run Timsort, which is merge sort with insertion sort for short runs and a trick for exploiting runs that are already ordered.

Against the quadratic three: at n = 60 merge sort does around 300 comparisons where selection sort does exactly 1,770. Push the slider to 60 and compare the counters.