Merge-insertion sort: Difference between revisions

Revision as of 18:26, 15 October 2020

Revision as of 20:16, 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}} Forand 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}} StanisławThe Trybułasame and Czen Pingalgorithm may have also been independently discovered theby same[[Stanisław algorithmTrybuła]] and Czen Ping.{{r|knuth}}

==Algorithm==