A merge sort (or collation sort) is the combination of two or more ordered lists into a single ordered list (Knuth 1998, p. 158). Merge sorting was one of the first methods proposed for computer sorting, and was first proposed by John von Neumann in 1945 (Knuth 1998, p. 159). Variants include two-way, natural two-way, straight two-way, and list merge sorts.
The minimum number of comparisons needed for a merge sort of elements for , 2, ... are 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ...
(OEIS A001768). An upper limit is given by the sequence
(1)
where
(2)
where is the floor
function (Steinhaus 1999, pp. 55-56), or equivalently,
Knuth, D. E. "Sorting by Merging." §5.2.4 in The
Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed.
Reading, MA: Addison-Wesley, pp. 158-168, 1998.Sloane, N. J. A.
Sequences A001768/M2408 and A001855/M2433
in "The On-Line Encyclopedia of Integer Sequences."Steinhaus,
H. Mathematical
Snapshots, 3rd ed. New York: Dover, 1999.Woodall, A. D.
"Algorithm 45: An Internal Sorting Procedure Using a Two-Way Merge." Comput.
J.13, 110-111, 1970.Woodrum, L. J. "Internal Sorting
with Minimal Comparing." IBM Systems J.8, 189-203, 1969.
needed for a merge sort of 
elements for 
, 2, ... are 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ...
(OEIS A001768). An upper limit 
is given by the sequence
is the floor
function (Steinhaus 1999, pp. 55-56), or equivalently,
![b(n)=sum_(k=1)^n[log_2k],](/images/equations/MergeSort/NumberedEquation3.svg)
