Merge-insertion sort: Difference between revisions

Revision as of 21:07, 13 August 2018

Revision as of 21:08, 13 August 2018

Line 1:

In [[computer science]], '''merge-insertinsertion 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}} 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==

Merge-insertinsertion sort performs the following steps, on an input <math>X</math> of <math>n</math> elements:<ref>The original description by {{harvtxt|Ford|Johnson|1959}} sorted the elements in descending order. The steps listed here reverse the output, following the description in {{harvtxt|Knuth|1998}}. The resulting algorithm makes the same comparisons but produces ascending order instead.</ref>

#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.

Line 20:

==Analysis==

Let <math>C(n)</math> denote the number of comparisons that merge-insertinsertion sort makes, in the worst case, when sorting <math>n</math> elements.

This number of comparisons can be broken down as the sum of three terms:

*<math>\lfloor n/2\rfloor</math> comparisons among the pairs of items,

Line 34:

==Relation to other comparison sorts==

The algorithm is called merge-insertinsertion sort because the initial comparisons that it performs before its recursive call (pairing up arbitrary items and comparing each pair) are the same as the initial comparisons of [[merge sort]],

while the comparisons that it performs after the recursive call (using binary search to insert elements one by one into a sorted list) follow the same principal as [[insertion sort]]. In this sense, it is a [[hybrid algorithm]] that combines both merge sort and insertion sort.<ref>{{harvtxt|Knuth|1998}}, p. 184: "Since it involves some aspects of merging and some aspects of insertion, we call it ''merge insertion''."</ref>

For small inputs (up to <math>n=11</math>) its numbers of comparisons equal the [[lower bound]] on comparison sorting of <math>\lceil\log_2 n!\rceil\approx n\log_2 n - 1.443n</math>. However, for larger inputs the number of comparisons made by the merge-insertinsertion algorithm is bigger than this lower bound.

Merge-insertinsertion sort also performs fewer comparisons than the [[sorting number]]s, which count the comparisons made by binary insertion sort or merge sort in the worst case. The sorting numbers fluctuate between <math>n\log_2 n - 0.915n</math> and <math>n\log_2 n - n</math>, with the same leading term but a worse constant factor in the lower-order linear term.{{r|fj}}

Merge insert sort is the sorting algorithm with the fewest possible comparisons for <math>n</math> items whenever <math>n\le 14</math>, and for <math>20\le n\le 22</math>.{{r|pec}}

For 20 years, merge-insertinsertion sort was the sorting algorithm with the fewest comparisons known for all input lengths.

However, in 1979 Glenn Manacher published another sorting algorithm that used even fewer comparisons, for large enough inputs.{{r|distrib|nonopt}}

It remains unknown exactly how many comparisons are needed for sorting, for all <math>n</math>, but Manacher's algorithm

and later record-breaking sorting algorithms have all used modifications of the merge-insertinsertion sort ideas.{{r|distrib}}

==References==