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\} \]