Assume (for simplicity in this exercise) that only one tuple fits in a block
and memory holds at most 3 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).
Answer: We will refer to the tuples (kangaroo, 17) through (baboon, 12)
using tuple numbers t1 through t12. We refer to the j
th run used by the i
th
pass, as ri j . The initial sorted runs have three blocks each. They are:
r11 = {t3, t1, t2}
r12 = {t6, t5, t4}
r13 = {t9, t7, t8}
r14 = {t12, t11, t10}
Each pass merges three runs. Therefore the runs after the end of the first
pass are:
r21 = {t3, t1, t6, t9, t5, t2, t7, t4, t8}
r22 = {t12, t11, t10}
At the end of the second pass, the tuples are completely sorted into one
run:
r31 = {t12, t3, t11, t10, t1, t6, t9, t5, t2, t7, t4, t8