TOPICS
Search

Merge Sort


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 a(n) needed for a merge sort of n elements for n=1, 2, ... are 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... (OEIS A001768). An upper limit b(n) is given by the sequence

 a(n)<=b(n)=1+kn-2^k
(1)

where

 k=|_log_2n_|+1,
(2)

where |_x_| is the floor function (Steinhaus 1999, pp. 55-56), or equivalently,

 b(n)=sum_(k=1)^n[log_2k],
(3)

giving 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, ... (OEIS A001855).


See also

Sorting

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Merge Sort

Cite this as:

Weisstein, Eric W. "Merge Sort." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MergeSort.html

Subject classifications