Content deleted Content added
Follow Knuthian nomenclature |
→Analysis: combine formulas |
||
Line 26:
*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 <math>S</math> of length at most three. First, <math>y_4</math> is inserted into the three-element subsequence <math>(x_1,x_2,x_3)</math>. Then, <math>y_3</math> is inserted into some permutation of the three-element subsequence <math>(x_1,x_2,y_4)</math>, or in some cases into the two-element subsequence <math>(x_1,x_2)</math>. Similarly, the elements <math>y_6</math> and <math>y_5</math> 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 <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}} 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 <math>C(n)</math>, giving the formula
:<math>C(n)=\sum_{i=1}^n \left\lceil \log_2 \frac{3i}{4} \right\rceil \approx n\log_2 n - 1.415n.</math><ref>{{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}}.</ref>
For <math>n=1,2,\dots</math> the numbers of comparisons are{{r|fj}}
:0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, 34, ... {{OEIS|A001768}}
==Relation to other comparison sorts==
| |||