Content deleted Content added
→Analysis: which algorithm |
optimality |
||
Line 34:
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.
Merge-insert sort 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}}
==Optimality==
For 20 years, merge-insert sort was the sorting algorithm with the fewest comparisons known (in the worst case, for each input length).
However, in 1979 Glenn Manacher published another sorting algorithm that used even fewer comparisons, for large enough inputs.{{r|distrib|nonopt}}
It remains unknown exactly how many comparisons are needed for sorting, for all <math>n</math>, but Manacher's algorithm
and later record-breaking sorting algorithms have all used modifications of the merge-insert sort ideas.{{r|distrib}}
==References==
| |||