Content deleted Content added
The third step of the algorithm (about the recursive call) now explicitly states that you have to use the merge-insertion recursively (this part was confusing and led to a lot of misimplementation around me). The Art of Computer Programming, 3rd volume by Donald Knuth explicitly states that the recursion must be made using the merge-insertion algorithm (page 184), and not a mere merge sort |
add animation gif |
||
Line 1:
{{Short description|Type of comparison sorting algorithm}}
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 [[Stanisław Trybuła]] and Czen Ping.{{r|knuth}}
[[File:Ford-janson.gif|thumb|An animation of the [[Merge algorithm|merge-algorithm]] sorting an array of randomized values.]]
==Algorithm==
| |||