|
==Analysis==
IfLet <math>C(n)</math> denote the number of comparisons that this algorithmmakes, isin usedthe toworst sortcase, when sorting <math>n</math> elements,.
let <math>C(n)</math> denote theThis number of comparisons thatcan be broken down as the sum of itthree makes.terms:
Then*<math>\lfloor this number ofn/2\rfloor</math> comparisons can be analyzed asamong the sumpairs of three terms:items,
*<math>C(\lfloor n/2\rfloor)</math> comparisons amongfor the pairsrecursive of itemscall,
<math>C(\lfloor*Some n/2\rfloor)</math>number of comparisons for the recursivebinary insertions used to insert the remaining call,elements.
and some number of comparisons forIn the binarythird insertions used to insertterm, 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 <math>S</math> of length at most three. SimilarlyMore generally, the worst-case number of comparisons for the elements in the <math>i</math>th group is <math>i+1</math>, because each is inserted into a subsequence of length at most <math>2^{i+1}-1</math>.{{r|fj|c4cs|distrib}}
This analysis can be used to compute the values of <math>C(n)</math>. For <math>n=1,2,\dots</math> they are{{r|fj}}
Based on this, the number of comparisons used by the algorithm
on an <math>n</math>-element input
can be described by the [[integer sequence]] (starting with <math>n=1</math>){{r|fj}}
:0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... {{OEIS|A001768}}
[[Asymptotic analysis|Asymptotically]], these numbers are approximately{{r|fj}}
:<math>n\log_2 n - 1.415n</math>
TheFor numbersmall inputs (up to <math>n=11</math>) these numbers of comparisons agrees withequal the [[lower bound]] on comparison sorting of <math>\lceil\log_2 n!\rceil\approx n\log_2 n - 1.443n</math>. up to <math>n=11</math>However, but diverges for larger valuesinputs the number of <math>n</math>comparisons made by the merge-insert algorithm is bigger than this lower bound.
ItThe algorithm also comparesperforms favorablyfewer withcomparisons than the [[sorting number]]s, thewhich numberscount ofthe comparisons made by binary insertion sort or merge sort in the worst case. The sorting numbers fluctuate between <math>n\log_2 n - 0.915n</math> and <math>n\log_2 n - n</math>, with the same leading term but a worse constant factor in the lower-order linear term.{{r|fj}}
which are approximately <math>n\log_2 n - 0.915n</math> for certain values of <math>n</math>.{{r|fj}}
==References==
| 