Merge-insertion sort: Difference between revisions

Revision as of 21:00, 13 August 2018

Revision as of 21:02, 13 August 2018

Line 32:

[[Asymptotic analysis|Asymptotically]], these numbers are approximately{{r|fj}}

:<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.

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

==Relation to other comparison sorts==

The algorithm is called merge-insert sort because the initial comparisons that it performs before its recursive call (pairing up arbitrary items and comparing each pair) are the same as the initial comparisons of [[merge sort]],

while the comparisons that it performs after the recursive call (using binary search to insert elements one by one into a sorted list) follow the same principal as [[insertion sort]]. In this sense, it is a [[hybrid algorithm]] that combines both merge sort and insertion sort.<ref>{{harvtxt|Knuth|1998}}, p. 184: "Since it involves some aspects of merging and some aspects of insertion, we call it ''merge insertion''."</ref>

For small inputs (up to <math>n=11</math>) theseits 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}}

Merge insert sort is the sorting algorithm with the fewest possible comparisons for <math>n</math> items whenever <math>n\le 14</math>, and for <math>20\le n\le 22</math>.{{r|pec}}