We can draw recursion tree in 2 ways:
1) By being biased on the right sub-array during partition with odd number of elements. This would give 20,47,15,8,9,4,40,30,12,17 after 2 calls to merge function.
2) By being biased on the left sub-array during partition with odd number of elements. This would give 15,20,47,8,9,4,40,30,12,17 after 2 calls to merge function.
I think in the question they are talking about iterative mergesort. Reference: https://www.geeksforgeeks.org/iterative-merge-sort/
// Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start=0; left_start<n-1; left_start += 2*curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = min(left_start + curr_size - 1, n-1);
int right_end = min(left_start + 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
By 2 passes they mean to say 2 iterations of the outer for loop in the above code.
First iteration of the outer for loop would merge all 1-sized array elements.
Second iteration of the outer for loop would merge all 2-sized array elements.
