Merge-insertion sort

In computer science, merge-insert sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson.^[1][2][3] It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort,^[1] and for 20 years it was the sorting algorithm with the fewest known comparisons.^[4] Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons.^[3]

Algorithm

Merge-insert sort performs the following steps, on an input ${\displaystyle X}$  of ${\displaystyle n}$  elements:^[1][2][3]

1. Group the elements of ${\displaystyle X}$  into ${\displaystyle \lfloor n/2\rfloor }$  pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements.
2. Perform ${\displaystyle \lfloor n/2\rfloor }$  comparisons, one per pair, to determine the larger of the two elements in each pair.
3. Recursively sort the ${\displaystyle \lfloor n/2\rfloor }$  elements found to be larger, creating a sorted sequence ${\displaystyle S}$  of ${\displaystyle \lfloor n/2\rfloor }$  of the input elements, in ascending order.
4. Insert at the start of ${\displaystyle S}$  the element that was paired with the first and smallest element of ${\displaystyle S}$ .
5. Insert the remaining ${\displaystyle \lceil n/2\rceil -1}$  elements of ${\displaystyle X\setminus S}$  into ${\displaystyle S}$ , one at a time, with a specially chosen insertion ordering described below. Use binary search in ${\displaystyle S}$  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 ${\displaystyle S}$  are most efficient when the subsequence of ${\displaystyle S}$  that is searched has a length that is one less than a power of two. To order the elements in such a way as to get binary searches of these lengths, consider the sorted sequence ${\displaystyle S}$  after step 4 of the outline above (before inserting the remaining elements), and let ${\displaystyle x_{i}}$  denote the ${\displaystyle i}$ th element of this sorted sequence. Thus,

${\displaystyle S=(x_{1},x_{2},x_{3},\dots ),}$ 

and each element ${\displaystyle x_{i}}$  with ${\displaystyle i\geq 3}$  has a corresponding element ${\displaystyle y_{i}}$ , known to be smaller than ${\displaystyle x_{i}}$ , that has not yet been inserted into the sequence. If ${\displaystyle n}$  is odd, the remaining unpaired element should also be numbered as one of the elements ${\displaystyle y_{i}}$ , with an index greater by one than the largest index of a paired element. With these indices defined, the final step of the outline above can be expanded into the following steps:^[1][2][3]

• Partition the uninserted elements ${\displaystyle y_{i}}$  into groups with contiguous indexes. There are two elements ${\displaystyle y_{3}}$  and ${\displaystyle y_{4}}$  in the first group, and the size of each subsequent group equals the number of elements in all previous groups. Thus, the sizes of the groups form a sequence of powers of two: 2, 2, 4, 8, 16, ...
• 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

${\displaystyle y_{4},y_{3},y_{6},y_{5},y_{10},y_{9},y_{8},y_{7},y_{18},\dots }$ 

• Use this ordering to insert the elements ${\displaystyle y_{i}}$  into ${\displaystyle S}$ . For each element ${\displaystyle y_{i}}$ , use a binary search from the start of ${\displaystyle S}$  up to but not including ${\displaystyle x_{i}}$  to determine where to insert ${\displaystyle y_{i}}$ .

Analysis

If this algorithm is used to sort ${\displaystyle n}$  elements, let ${\displaystyle C(n)}$  denote the number of comparisons that it makes. Then this number of comparisons can be analyzed as the sum of three terms: ${\displaystyle \lfloor n/2\rfloor }$  comparisons among the pairs of items, ${\displaystyle C(\lfloor n/2\rfloor )}$  comparisons for the recursive call, and some number of comparisons for the binary insertions used to insert the remaining elements. The worst-case number of comparisons for the elements in the first group is two, because each is inserted into a subsequence of ${\displaystyle S}$  of length at most three. Similarly, the worst-case number of comparisons for the elements in the ${\displaystyle i}$ th group is ${\displaystyle i+1}$ , because each is inserted into a subsequence of length at most ${\displaystyle 2^{i+1}-1}$ .^[1][2][3]

Based on this, the number of comparisons used by the algorithm on an ${\displaystyle n}$ -element input can be described by the integer sequence (starting with ${\displaystyle n=1}$ )^[1]

0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... (sequence A001768 in the OEIS)

Asymptotically, these numbers are approximately^[1]

${\displaystyle n\log _{2}n-1.415n}$ 

The number of comparisons agrees with the lower bound on comparison sorting of ${\displaystyle \lceil \log _{2}n!\rceil \approx n\log _{2}n-1.443n}$  up to ${\displaystyle n=11}$ , but diverges for larger values of ${\displaystyle n}$ . It also compares favorably with the sorting numbers, the numbers of comparisons made by binary insertion sort or merge sort in the worst case, which are approximately ${\displaystyle n\log _{2}n-0.915n}$ .^[1]

References

1. Ford, Lester R. Jr.; Johnson, Selmer M. (1959), "A tournament problem", American Mathematical Monthly, 66: 387–389, doi:10.2307/2308750, MR 0103159
2. Williamson, Stanley Gill (2002), "2.31 Merge insertion (Ford–Johnson)", Combinatorics for Computer Science, Dover books on mathematics, Courier Corporation, pp. 66–68, ISBN 9780486420769
3. Mahmoud, Hosam M. (2011), "12.3.1 The Ford–Johnson algorithm", Sorting: A Distribution Theory, Wiley Series in Discrete Mathematics and Optimization, vol. 54, John Wiley & Sons, pp. 286–288, ISBN 9781118031131
4. Manacher, Glenn K. (July 1979), "The Ford-Johnson Sorting Algorithm Is Not Optimal", Journal of the ACM, 26 (3): 441–456, doi:10.1145/322139.322145