Content deleted Content added
(edit summary removed) |
The original 2, 2, 4, 8, 16 is incorrect, see: <ref>https://linuxnasm.be/media/pdf/donald-knuth/taocp/volume-3/taocp-vol3-sorting-searching.pdf#page=245</ref> |
||
Line 16:
*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 sums of sizes of every two adjacent groups form a sequence of powers of two. Thus, the sizes of groups are: 2, 2, 6, 10, 22, 42, ...
*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_{22},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>.
| |||