Merge-insertion sort: Difference between revisions

Revision as of 17:18, 10 November 2021

Latest revision as of 15:17, 30 October 2024

(19 intermediate revisions by 12 users 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==

Hello Khaled !

Merge-insertion 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.

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

Line 41 ⟶ 42:

Merge-insertion 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-insertion sort is the sorting algorithm with the minimum possible comparisons for <math>n</math> items whenever <math>n\le 15</math> or <math>20\le n\le 22</math>, and it has the fewest comparisons known for <math>n\le 46</math>.{{r|pec|pec2}}

For 20 years, merge-insertion 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}}

Line 111 ⟶ 112:

| pages = 441–456

| title = The Ford-Johnson Sorting Algorithm Is Not Optimal

| volume = 26}}</ref>| doi-access = free

}}</ref>

<ref name=pec>{{citation

Line 140 ⟶ 142:

[[Category:Comparison sorts]]

[[Category:1959 in computing]]

[[Category:Sorting algorithms]]