TAOCP 5.2.1 Exercise 32

The list insertion sort (Algorithm L) applied to the 16 keys from Table 1 (503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703) produces the following final link array \(L_0...

taocpmathematicsalgorithmsvolume-3simple

Section 5.2.1: Sorting by Insertion

Exercise 32. [10] What would be the final contents of $L_0, L_1 \ldots L_{16}$ if the list insertion sort in Table 8 were carried through to completion?

Verified: no
Solve time: 4m23s

The list insertion sort (Algorithm L) applied to the 16 keys from Table 1 (503, 087, 512, 061, 908, 170, 897, 275, 653, 426, 154, 509, 612, 677, 765, 703) produces the following final link array (L_0, L_1, \ldots, L_{16}):

[ \boxed{4,\ 12,\ 11,\ 13,\ 2,\ 0,\ 8,\ 5,\ 10,\ 14,\ 1,\ 6,\ 3,\ 9,\ 16,\ 7,\ 15} ]

That is, (L_0 = 4), (L_1 = 12), (L_2 = 11), (L_3 = 13), (L_4 = 2), (L_5 = 0), (L_6 = 8), (L_7 = 5), (L_8 = 10), (L_9 = 14), (L_{10} = 1), (L_{11} = 6), (L_{12} = 3), (L_{13} = 9), (L_{14} = 16), (L_{15} = 7), (L_{16} = 15). ∎