Merge-insertion sort
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 formula_1 of formula_2 elements: The algorithm is designed to take advantage of the fact that the binary searches used to insert elements into formula_7 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  formula_7 after step 4 of the outline above (before inserting the remaining elements), and let formula_17 denote the formula_18th element of this sorted sequence. Thus, where each element formula_17 with formula_21 is paired with an element formula_22 that has not yet been inserted. (There are no elements formula_23 or formula_24 because formula_25 and formula_26 were paired with each other.) If formula_2 is odd, the remaining unpaired element should also be numbered as formula_28 with formula_18 larger than the indexes of the paired elements. Then, the final step of the outline above can be expanded into the following steps: Analysis. Let  formula_40 denote the number of comparisons that merge-insertion sort makes, in the worst case, when sorting formula_2 elements. This number of comparisons can be broken down as the sum of three terms: In the third term, the worst-case number of comparisons for the elements in the first group is two, because each is inserted into a subsequence of formula_7 of length at most three. First, formula_32 is inserted into the three-element subsequence formula_46. Then, formula_31 is inserted into some permutation of the three-element subsequence formula_48, or in some cases into the two-element subsequence formula_49. Similarly , the elements formula_50 and formula_51 of the second group are each inserted into a subsequence of length at most seven, using three comparisons. More generally, the worst-case number of comparisons for the elements in the formula_18th group is formula_53, because each is inserted into a subsequence of length at most formula_54. By summing the number of comparisons used for all the elements and solving the resulting recurrence relation, this analysis can be used to compute the values of formula_40, giving the formula or, in closed form, For formula_58 the numbers of comparisons are Relation to other comparison sorts. The  algorithm is called merge-insertion 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 principle as insertion sort. In this sense, it is a hybrid algorithm that combines both merge sort and insertion sort. For small inputs (up to formula_59) its numbers of comparisons equal the lower bound on comparison sorting of formula_60 . However, for larger inputs the number of comparisons made by the merge-insertion algorithm is bigger than this lower bound. Merge-insertion sort also performs fewer comparisons than the sorting numbers, which count the comparisons made by binary insertion sort or merge sort in the worst case. The sorting numbers fluctuate between formula_61 and formula_62, with the same leading term but a worse constant factor in the lower-order linear term. Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for formula_2 items whenever formula_64 or formula_65, and it has the fewest comparisons known for formula_66. 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. It remains unknown exactly how many comparisons are needed for sorting, for all formula_2, but Manacher's algorithm and later record-breaking sorting algorithms have all used modifications of the merge-insertion sort ideas.