15.1

Assume (for simplicity in this exercise) that only one tuple fits in a block and memory holds at most three blocks. Show the runs created on each pass of the sort-merge algorithm when applied to sort the following tuples on the first attribute: (kangaroo, 17), (wallaby, 21), (emu, 1), (wombat, 13), (platypus, 3), (lion, 8), (warthog, 4), (zebra, 11), (meerkat, 6), (hyena, 9), (hornbill, 2), (baboon, 12).

---

We will refer to the tuples (kangaroo, 17) through (baboon, 12) using tuple numbers $t_1$ through $t_{12}$. We refer 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_{11}=\{t_3,t_1,t_2\}$$ $$r_{12}=\{t_6,t_5,t_4\}$$ $$r_{13}=\{t_9,t_7,t_8\}$$ $$r_{14}=\{t_{12},t_{11},t_{10}\}$$

Each pass merges three runs. Therefore the runs after the end of the first pass are:

$$r_{21}=\{t_3,t_1,t_6,t_9,t_5,t_2,t_7,t_4,t_8\}$$ $$r_{22}=\{t_{12},t_{11},t_{10}\}$$

At the end of the second pass, the tuples are completely sorted into one run:

$$r_{31}=\{t_{12},t_3,t_{11},t_{10},t_1,t_6,t_9,t_5,t_2,t_7,t_4,t_8\}$$