Merge-insertion sort

Merge-insertion sort performs the following steps, on an input $X$ of $n$ elements: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.

1. Group the elements of $X$ into $\backslash lfloor\; n/2\backslash rfloor$ pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements.
2. Perform $\backslash lfloor\; n/2\backslash rfloor$ comparisons, one per pair, to determine the larger of the two elements in each pair.
3. Recursively sort the $\backslash lfloor\; n/2\backslash rfloor$ larger elements from each pair, creating a sorted sequence $S$ of $\backslash lfloor\; n/2\backslash rfloor$ of the input elements, in ascending order, using the merge-insertion sort.
4. Insert at the start of $S$ the element that was paired with the first and smallest element of $S$.
5. Insert the remaining $\backslash lceil\; n/2\backslash rceil-1$ elements of $X\backslash setminus\; S$ into $S$, one at a time, with a specially chosen insertion ordering described below. Use binary search in subsequences of $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$ 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.{{r|fj}} To choose an insertion ordering that produces these lengths, consider the sorted sequence $S$ after step 4 of the outline above (before inserting the remaining elements),

and let $x\_i$ denote the $i$th element of this sorted sequence. Thus,

:$S=(x\_1,x\_2,x\_3,\backslash dots),$

where each element $x\_i$ with $i\backslash ge\; 3$ is paired with an element that has not yet been inserted. (There are no elements $y\_1$ or $y\_2$ because $x\_1$ and $x\_2$ were paired with each other.) If $n$ is odd, the remaining unpaired element should also be numbered as $y\_i$ with $i$ 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 $y\_i$ into groups with contiguous indexes. There are two elements $y\_3$ and $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

::$y\_4,y\_3,y\_6,y\_5,y\_\{12\},y\_\{11\},y\_\{10\},y\_9,y\_8,y\_7,y\_\{22\},y\_\{21\}\backslash dots$

• Use this ordering to insert the elements $y\_i$ into $S$. For each element $y\_i$, use a binary search from the start of $S$ up to but not including $x\_i$ to determine where to insert $y\_i$.

Let $C(n)$ denote the number of comparisons that merge-insertion sort makes, in the worst case, when sorting $n$ elements.

This number of comparisons can be broken down as the sum of three terms:

• $\backslash lfloor\; n/2\backslash rfloor$ comparisons among the pairs of items,
• $C(\backslash lfloor\; n/2\backslash rfloor)$ comparisons for the recursive call, and
• some number of comparisons for the binary insertions used to insert the remaining elements.

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 $S$ of length at most three. First, $y\_4$ is inserted into the three-element subsequence $(x\_1,x\_2,x\_3)$. Then, $y\_3$ is inserted into some permutation of the three-element subsequence $(x\_1,x\_2,y\_4)$, or in some cases into the two-element subsequence $(x\_1,x\_2)$. Similarly, the elements $y\_6$ and $y\_5$ 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 $i$th group is $i+1$, because each is inserted into a subsequence of length at most $2^\{i+1\}-1$.{{r|fj|c4cs|distrib|knuth}} 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 $C(n)$, giving the formula{{harvtxt|Knuth|1998}} credits the summation formula to the 1960 Ph.D. thesis of A. Hadian. The approximation formula was already given by {{harvtxt|Ford|Johnson|1959}}.

:$C(n)=\backslash sum\_\{i=1\}^n\; \backslash left\backslash lceil\; \backslash log\_2\; \backslash frac\{3i\}\{4\}\; \backslash right\backslash rceil\; \backslash approx\; n\backslash log\_2\; n\; -\; 1.415n$

or, in closed form,{{r|gn}}

:$C(n)=n\backslash biggl\backslash lceil\backslash log\_2\backslash frac\{3n\}\{4\}\backslash biggr\backslash rceil-\backslash biggl\backslash lfloor\backslash frac\{2^\{\backslash lfloor\; \backslash log\_2\; 6n\backslash rfloor\}\}\{3\}\backslash biggr\backslash rfloor+\backslash biggl\backslash lfloor\backslash frac\{\backslash log\_2\; 6n\}\{2\}\backslash biggr\backslash rfloor.$

For $n=1,2,\backslash dots$ the numbers of comparisons are{{r|fj}}

:0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... {{OEIS|A001768}}

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.{{harvtxt|Knuth|1998}}, p. 184: "Since it involves some aspects of merging and some aspects of insertion, we call it merge insertion."

For small inputs (up to $n=11$) its numbers of comparisons equal the lower bound on comparison sorting of $\backslash lceil\backslash log\_2\; n!\backslash rceil\backslash approx\; n\backslash log\_2\; n\; -\; 1.443n$. 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 $n\backslash log\_2\; n\; -\; 0.915n$ and $n\backslash log\_2\; n\; -\; n$, 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 $n$ items whenever $n\backslash le\; 22$, and it has the fewest comparisons known for $n\backslash le\; 46$.{{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}}

It remains unknown exactly how many comparisons are needed for sorting, for all $n$, but Manacher's algorithm

and later record-breaking sorting algorithms have all used modifications of the merge-insertion sort ideas.{{r|distrib}}

{{reflist|refs=

{{citation

| last = Williamson | first = Stanley Gill

| contribution = 2.31 Merge insertion (Ford–Johnson)

| contribution-url = https://books.google.com/books?id=YMIoy5JwdHMC&pg=PA66

| isbn = 9780486420769

| pages = 66–68

| publisher = Courier Corporation

| series = Dover books on mathematics

| title = Combinatorics for Computer Science

| year = 2002}}

{{citation

| last = Mahmoud | first = Hosam M.

| contribution = 12.3.1 The Ford–Johnson algorithm

| contribution-url = https://books.google.com/books?id=kM5v2YqMVuoC&pg=PA286

| isbn = 9781118031131

| pages = 286–288

| publisher = John Wiley & Sons

| series = Wiley Series in Discrete Mathematics and Optimization

| title = Sorting: A Distribution Theory

| volume = 54

| year = 2011}}

{{citation

| last1 = Ford | first1 = Lester R. Jr. | author1-link = L. R. Ford Jr.

| last2 = Johnson | first2 = Selmer M. | author2-link = Selmer M. Johnson

| doi = 10.2307/2308750

| journal = American Mathematical Monthly

| mr = 0103159

| pages = 387–389

| title = A tournament problem

| volume = 66

| year = 1959}}

{{citation

| last1 = Guy | first1 = Richard K. | author1-link = Richard K. Guy

| last2 = Nowakowski | first2 = Richard J.

| date = December 1995

| doi = 10.2307/2975272

| issue = 10

| journal = American Mathematical Monthly

| pages = 921–926

| title = Monthly Unsolved Problems, 1969-1995

| volume = 102}}

{{citation

| last = Knuth | first = Donald E. | author-link = Donald Knuth

| contribution = Merge insertion

| edition = 2nd

| pages = 184–186

| title = The Art of Computer Programming, Vol. 3: Sorting and Searching

| year = 1998}}

{{citation

| last = Manacher | first = Glenn K.

| date = July 1979

| doi = 10.1145/322139.322145

| issue = 3

| journal = Journal of the ACM

| pages = 441–456

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

| volume = 26| doi-access = free

}}

{{citation

| last = Peczarski | first = Marcin

| doi = 10.1007/s00453-004-1100-7

| issue = 2

| journal = Algorithmica

| mr = 2072769

| pages = 133–145

| title = New results in minimum-comparison sorting

| volume = 40

| year = 2004}}

{{citation

| last = Peczarski | first = Marcin

| doi = 10.1016/j.ipl.2006.09.001

| issue = 3

| journal = Information Processing Letters

| mr = 2287331

| pages = 126–128

| title = The Ford-Johnson algorithm still unbeaten for less than 47 elements

| volume = 101

| year = 2007}}

}}

{{Sorting}}

Category:Comparison sorts

Category:1959 in computing