Merge-insertion sort: Difference between revisions

Revision as of 21:16, 13 August 2018

Revision as of 21:29, 13 August 2018

Line 38:

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 fewestminimum possible comparisons for <math>n</math> items whenever <math>n\le 1415</math>, and foror <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}}

Line 109:

| volume = 40

| year = 2004}}</ref>

<ref name=pec2>{{citation

| last = Peczarski | first = Marcin

| doi = 10.1016/j.ipl.2006.09.001

| issue = 3

| journal = Information Processing Letters

| mr = 2287331

| pages = 126–128

| title = The Ford-Johnson algorithm still unbeaten for less than 47 elements

| volume = 101

| year = 2007}}</ref>

}}