Merge sort (or collation sort) is a sorting algorithm that sorts smaller groups of items and merges the resulting ordered lists into a single ordered list (Knuth 1998, p. 158). In the two-way version, the items are split into two groups, each group is sorted recursively, and the two ordered lists are merged. Knuth (1998, p. 159) credits John von Neumann with proposing merge sort in 1945. Variants include natural two-way, straight two-way, and list merge sorts.
For balanced two-way merge sort, the maximum number of comparisons 
needed to sort 
distinct elements is
 |
where 
and 
is the floor function
(Steinhaus 1999, pp. 55-56). Equivalently,
![b(n)=sum_(j=1)^n[log_2j],](/images/equations/MergeSort/NumberedEquation2.svg) |
where ![[x]](/images/equations/MergeSort/Inline5.svg)
is the ceiling
function, giving 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, ... (OEIS A001855)
for 
, 2, ....
The different sequence 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... (OEIS A001768) gives the maximum number of comparisons used by Ford-Johnson merge-insertion sort (Ford and Johnson 1959), which combines merging with insertion sorting. It does not give the comparison count for ordinary merge sort.
