Merge-insertion sort: Difference between revisions

Revision as of 21:15, 13 August 2018

Revision as of 21:16, 13 August 2018

Line 1:

In [[computer science]], '''merge-insertion sort''' or the '''Ford–Johnson algorithm''' is a [[comparison sort]]ing algorithm published in 1959 by [[L. R. Ford Jr.]] and [[Selmer M. Johnson]].{{r|fj|c4cs|distrib|knuth}} It uses fewer comparisons in the [[worst case analysis|worst case]] than the best previously known algorithms, [[insertion sort|binary insertion sort]] and [[merge sort]],{{r|fj}} and for 20 years it was the sorting algorithm with the fewest known comparisons.{{r|nonopt}} Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons.{{r|distrib}} The same algorithm may have also been independently discovered by S. Trybula and P. Czen.{{r|knuth}}

==Algorithm==