GATE CS 1999 Q1.14 — Searching, Sorting, Hashing

In a straight two-way merge sort (also known as iterative or bottom-up merge sort), we start by considering each element as a sorted run of size $1$. In each subsequent pass, we merge adjacent sorted runs of size $2^{k-1}$ to form sorted runs of size $2^k$.

Let's trace the algorithm step-by-step for the given array:

$$\text{Initial Array: } [20], [47], [15], [8], [9], [4], [40], [30], [12], [17]$$

Pass 1:

Merge adjacent runs of size $1$ to form sorted runs of size $2$:

• Merge $[20]$ and $[47] \implies [20, 47]$
• Merge $[15]$ and $[8] \implies [8, 15]$
• Merge $[9]$ and $[4] \implies [4, 9]$
• Merge $[40]$ and $[30] \implies [30, 40]$
• Merge $[12]$ and $[17] \implies [12, 17]$

Array after Pass 1:

$$20, \ 47, \ 8, \ 15, \ 4, \ 9, \ 30, \ 40, \ 12, \ 17$$

Pass 2:

Merge adjacent runs of size $2$ to form sorted runs of size $4$:

• Merge $[20, 47]$ and $[8, 15] \implies [8, 15, 20, 47]$
• Merge $[4, 9]$ and $[30, 40] \implies [4, 9, 30, 40]$
• The remaining run $[12, 17]$ has no adjacent run to merge with, so it remains as is: $[12, 17]$

Array after Pass 2:

$$8, \ 15, \ 20, \ 47, \ 4, \ 9, \ 30, \ 40, \ 12, \ 17$$

This matches the sequence given in Option B.