Merge-insertion sort: Difference between revisions

Revision as of 13:20, 6 May 2019

Revision as of 17:47, 6 May 2019

Line 14:

where each element <math>x_i</math> with <math>i\ge 3</math> is paired with an element <math>y_i < x_i</math> that has not yet been inserted. (There are no elements <math>y_1</math> or <math>y_2</math> because <math>x_1</math> and <math>x_2</math> were paired with each other.) If <math>n</math> is odd, the remaining unpaired element should also be numbered as <math>y_i</math> with <math>i</math> larger than the indexes of the paired elements.

Then, the final step of the outline above can be expanded into the following steps:{{r|fj|c4cs|distrib|knuth}}

*Partition the uninserted elements <math>y_i</math> into groups with contiguous indexes. There are two elements <math>y_3</math> and <math>y_4</math> in the first group, and the sumssize of sizeseach ofsubsequent everygroup twoequals adjacentthe groupsnumber formof aelements sequencein ofall powers ofprevious twogroups. Thus, the sizes of the groups areform a sequence of powers of two: 2, 2, 6, 104, 228, 4216, ...

*Order the uninserted elements by their groups (smaller indexes to larger indexes), but within each group order them from larger indexes to smaller indexes. Thus, the ordering becomes

::<math>y_4,y_3,y_6,y_5,y_{12},y_{11},y_{10},y_9,y_8,y_7,y_{2218},y_{21}\dots</math>

*Use this ordering to insert the elements <math>y_i</math> into <math>S</math>. For each element <math>y_i</math>, use a binary search from the start of <math>S</math> up to but not including <math>x_i</math> to determine where to insert <math>y_i</math>.