1. Understanding Straight Two-Way Merge Sort
In an iterative or straight two-way merge sort, we process data sequentially in distinct passes. We do not use recursion. Instead, we begin by treating each single element as a sorted sublist of size 1 and merge adjacent pairs systematically:
Initial State: n sorted sublists, each containing exactly 1 element.
Pass 1: Groups adjacent sublists of size 1 and merges them into sorted runs of size 2.
Pass 2: Groups adjacent sublists of size 2 and merges them into sorted runs of size 4.
Pass 3: Groups adjacent sublists of size 4 and merges them into sorted runs of size 8, and so on.
2. Step-by-Step Execution Tracking
Initial Given Array (Size = 1)
{20},{47},{15},{8},{9},{4},{40},{30},{12},{17}
Pass 1: Merging pairs of size 1 into sorted runs of size 2
We combine adjacent individual elements pairwise:
Merge {20} and {47}→[20,47]
Merge {15} and {8}→[8,15]
Merge {9} and {4}→[4,9]
Merge {40} and {30}→[30,40]
Merge {12} and {17}→[12,17]
Array after Pass 1=[20,47],[8,15],[4,9],[30,40],[12,17]
Array after Pass 1=20,47,8,15,4,9,30,40,12,17
Pass 2: Merging pairs of size 2 into sorted runs of size 4
We take the sorted sublists of size 2 from Pass 1 and merge adjacent pairs together into sorted sequences of size 4:
Merge [20,47] and [8,15]→[8,15,20,47]
Merge [4,9] and [30,40]→[4,9,30,40]
The remaining sublist [12,17] has no adjacent partner of size 2 to pair with, so it is carried over unchanged →[12,17]
Array after Pass 2=[8,15,20,47],[4,9,30,40],[12,17]
3. Final Sequence Verification
Writing out the array elements sequentially after the second pass concludes gives:
8,15,20,47,4,9,30,40,12,17
Correct Answer
The correct option is (b) 8,15,20,47,4,9,30,40,12,17.
