Merge-insertion sort: Difference between revisions

Revision as of 03:39, 13 August 2018

Revision as of 03:43, 13 August 2018

Line 20:

==Analysis==

Let <math>C(n)</math> denote the number of comparisons that thismerge-insert sort makes, in the worst case, when sorting <math>n</math> elements.

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

*<math>\lfloor n/2\rfloor</math> comparisons among the pairs of items,