Merge-insertion sort: Difference between revisions

Revision as of 21:14, 13 August 2018

Revision as of 21:15, 13 August 2018

Line 33:

==Relation to other comparison sorts==

The algorithm is called merge-insertion 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 principalprinciple 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>) its 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-insertion algorithm is bigger than this lower bound.