Merge-insertion sort: Difference between revisions

Revision as of 03:50, 13 August 2018

Revision as of 03:50, 13 August 2018

Line 33:

:<math>n\log_2 n - 1.415n</math>

For small inputs (up to <math>n=11</math>) these numbers of comparisons equal the [[lower bound]] on comparison sorting of <math>\lceil\log_2 n!\rceil\approx n\log_2 n - 1.443n</math>. However, for larger inputs the number of comparisons made by the merge-insert algorithm is bigger than this lower bound.

TheMerge-insert algorithmsort also performs fewer comparisons than the [[sorting number]]s, which count the 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}}

==References==