Merge-insertion sort: Difference between revisions

Revision as of 17:49, 22 June 2023

Revision as of 01:46, 27 July 2023

Line 40:

Merge-insertion 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}}

Merge-insertion sort is the sorting algorithm with the minimum possible comparisons for <math>n</math> items whenever <math>n\le 15</math> or <math>20\le n\le 22</math>, and it has the fewest comparisons known for <math>n\le 46</math>.{{r|pec|pec2}}

For 20 years, merge-insertion sort was the sorting algorithm with the fewest comparisons known for all input lengths.

However, in 1979 Glenn Manacher published another sorting algorithm that used even fewer comparisons, for large enough inputs.{{r|distrib|nonopt}}