Merge-insertion sort: Difference between revisions

Revision as of 02:06, 31 May 2020

Revision as of 18:26, 15 October 2020

Line 1:

In [[computer science]], '''merge-insertion sort''' or the '''Ford–Johnson algorithm''' is a [[comparisonComparison sort|comparison sorting]]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 [[worstWorst case analysis|worst case]] than the best previously known algorithms, [[insertionInsertion sort|binary insertion sort]] and [[merge sort]],{{r|fj}}. and forFor 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}} TheStanisław sameTrybuła algorithmand Czen Ping may have also been independently discovered bythe [[Stanisławsame Trybuła]] and Czen Pingalgorithm.{{r|knuth}}

==Algorithm==