Merge-insertion sort: Difference between revisions

Revision as of 03:43, 13 August 2018

Revision as of 03:50, 13 August 2018

Line 25:

*<math>C(\lfloor n/2\rfloor)</math> comparisons for the recursive call,

*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]],

Thisthis analysis can be used to compute the values of <math>C(n)</math>. For <math>n=1,2,\dots</math> theythese values are{{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}}