Chapter 15, Problem 1PE

Explanation of Solution

Creation of runs on each pass of the sort-merge algorithm:

• The user will refer to the tuples (kangaroo, 17) through (baboon,12) using the tuple numbers “t₁” through “t₂”.
• The user refers to the j^th run used by the i^th pass as r_ij.
• The initial sorted runs have three blocks each. They are:

r₁₁ = {t₃, t₁, t₂}

r₁₂ = {t₆, t₅, t₄}

r₁₃ = {t₉, t₇, t₈}

r₁₄ = {t₁₂, t₁₁, t₁₀}

Here, each pass merges three runs.

Therefore, the runs after the end of the 1^st pass are:

r₂₁ = {t₃, t₁, t₆, t₉, t₅, t₂, t₇, t₄, t₈}

r₂₂ = {t₁₂, t₁₁, t₁₀}

At the end of the 2^nd pass, the tuples are completely sorted into one run:

r₃₁ = {t₁₂, t₃, t₁₁, t₁₀, t₁, t₆, t₉, t₅, t₂, t₇, t₄, t₈}