In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson. It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanisław Trybuła and Czen Ping.
Algorithm Merge-insertion sort performs the following steps, on an input X {\displaystyle X} of n {\displaystyle n} elements:
Group the elements of X {\displaystyle X} into ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements. Perform ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } comparisons, one per pair, to determine the larger of the two elements in each pair. Recursively sort the ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } larger elements from each pair, creating a sorted sequence S {\displaystyle S} of ⌊ n / 2 ⌋ {\displaystyle \lfloor n/2\rfloor } of the input elements, in ascending order, using the merge-insertion sort. Insert at the start of S {\displaystyle S} the element that was paired with the first and smallest element of S {\displaystyle S} . Insert the remaining ⌈ n / 2 ⌉ − 1 {\displaystyle \lceil n/2\rceil -1} elements of X ∖ S {\displaystyle X\setminus S} into S {\displaystyle S} , one at a time, with a specially chosen insertion ordering described below. Use binary search in subsequences of S {\displaystyle S} (as described below) to determine the position at which each element should be inserted. The algorithm is designed to take advantage of the fact that the binary searches used to insert elements into S {\displaystyle S} are most efficient (from the point of view of worst case analysis) when the length of the subsequence that is searched is one less than a power of two. This is because, for those lengths, all outcomes of the search use the same number of comparisons as each other. To choose an insertion ordering that produces these lengths, consider the sorted sequence S {\displaystyle S} after step 4 of the outline above (before inserting the remaining elements), and let x i {\displaystyle x_{i}} denote the i {\displaystyle i} th element of this sorted sequence. Thus,
S = ( x 1 , x 2 , x 3 , … ) , {\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}
where each element x i {\displaystyle x_{i}} with i ≥ 3 {\displaystyle i\geq 3} is paired with an element y i < x i {\displaystyle y_{i}<x_{i}} that has not yet been inserted. (There are no elements y 1 {\displaystyle y_{1}} or y 2 {\displaystyle y_{2}} because x 1 {\displaystyle x_{1}} and x 2 {\displaystyle x_{2}} were paired with each other.) If n {\displaystyle n} is odd, the remaining unpaired element should also be numbered as y i {\displaystyle y_{i}} with i {\displaystyle i} larger than the indexes of the paired elements. Then, the final step of the outline above can be expanded into the following steps:
Partition the uninserted elements y i {\displaystyle y_{i}} into groups with contiguous indexes. There are two elements y 3 {\displaystyle y_{3}} and y 4 {\displaystyle y_{4}} 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
… excerpt ends here. Continue reading the full article.
