Content deleted Content added
No edit summary Tag: Reverted |
add animation gif |
||
| (12 intermediate revisions by 7 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==
Line 5 ⟶ 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.
Line 14 ⟶ 16:
where each element <math>x_i</math> with <math>i\ge 3</math> is paired with an element <math>y_i < x_i</math> that has not yet been inserted. (There are no elements <math>y_1</math> or <math>y_2</math> because <math>x_1</math> and <math>x_2</math> were paired with each other.) If <math>n</math> is odd, the remaining unpaired element should also be numbered as <math>y_i</math> with <math>i</math> larger than the indexes of the paired elements.
Then, the final step of the outline above can be expanded into the following steps:{{r|fj|c4cs|distrib|knuth}}
*Partition the uninserted elements <math>y_i</math> into groups with contiguous indexes. There are two elements <math>y_3</math> and <math>y_4</math> in the first group, and the sums of sizes of every two adjacent groups form a sequence of powers of two. Thus, the sizes of groups are: 2, 2, 6, 10, 22, 42, ...
*Order the uninserted elements by their groups (smaller indexes to larger indexes), but within each group order them from larger indexes to smaller indexes. Thus, the ordering becomes
::<math>y_4,y_3,y_6,y_5,y_{12},y_{11},y_{10},y_9,y_8,y_7,y_{22},y_{21}\dots</math>
Line 139 ⟶ 142:
[[Category:Comparison sorts]]
[[Category:1959 in computing]]
| |||