Content deleted Content added
→Analysis: reverted an eroneous change of mine |
add animation gif |
||
| (One intermediate revision by one other user not shown) | |||
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==
Line 6 ⟶ 7:
#Group the elements of <math>X</math> into <math>\lfloor n/2\rfloor</math> pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements.
#Perform <math>\lfloor n/2\rfloor</math> comparisons, one per pair, to determine the larger of the two elements in each pair.
#Recursively sort the <math>\lfloor n/2\rfloor</math> larger elements from each pair, creating a sorted sequence <math>S</math> of <math>\lfloor n/2\rfloor</math> of the input elements, in ascending order, using the merge-insertion sort.
#Insert at the start of <math>S</math> the element that was paired with the first and smallest element of <math>S</math>.
#Insert the remaining <math>\lceil n/2\rceil-1</math> elements of <math>X\setminus S</math> into <math>S</math>, one at a time, with a specially chosen insertion ordering described below. Use [[binary search]] in subsequences of <math>S</math> (as described below) to determine the position at which each element should be inserted.
| |||