Merge sort

Key facts and history

Merge sort has an average and worst-case performance of O(n log n) comparisons when sorting n objects.^[3] The recurrence relation T(n) = 2T(n/2) + n describes the running time, where n steps are taken to merge two lists of half the original size.^[3] In the worst case, merge sort uses approximately 39% fewer comparisons than quicksort does in its average case.^[4] Merge sort's most common implementation does not sort in place, requiring memory for the sorted output.^[3]

A natural merge sort exploits naturally occurring sorted runs in the input, unlike bottom-up merge sort which assumes each run is one item long.^[5] A ping-pong merge merges four blocks at a time instead of two, reducing the total number of moves by half.^[6] An early public domain implementation of a four-at-once merge was by WikiSort in 2014.^[6][7] WikiSort is a stable merge sort based on "Ratio based stable in-place merging" by Pok-Son Kim and Arne Kutzner.^[7]

Quadsort is a stable bottom-up adaptive branchless merge sort that starts with an analyzer to detect ordered data.^[8]

What the research sources say

The quadsort analyzer examines the array 8 elements at a time, using a method that should result in 0.2 branch mispredictions on random data on average.^[8] Reverse-order data can be sorted using n comparisons and n moves through run detection and a reversal routine.^[8] A parity merge can be fully unrolled and is suitable for branchless optimizations to speed up sorting of random data.^[8] The cross merge, which merges four items at a time, gives a decent performance gain for both ordered and random data.^[8]

The simplest parallel merge sort implementation outperforms both STL sort and stable_sort for arrays larger than about 10K elements.^[9] A hybrid parallel merge sort using insertion sort for sub-arrays of 48 elements or less accelerated the algorithm by over 2X for all array sizes.^[9] The parallel merge sort algorithm achieves a high degree of parallelism, Θ(n/lg² n), and is stable through the use of a stable sort as the recursion base case.^[9]