Problem:
Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4
Suppose we run MergeSort on this array. What is the number in the 7th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge step)? (When we say "7th" position, we're counting positions starting at 1; for example, the input array has a "0" in its 7th position.)
Solution:
Just before the last merge, the left half and the right half must be sorted, so it should be
1 3 5 8 9 0 2 4 6 7
Therefore the solution is 2.
Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4
Suppose we run MergeSort on this array. What is the number in the 7th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge step)? (When we say "7th" position, we're counting positions starting at 1; for example, the input array has a "0" in its 7th position.)
Solution:
Just before the last merge, the left half and the right half must be sorted, so it should be
1 3 5 8 9 0 2 4 6 7
Therefore the solution is 2.
Can you please provide the whole algorithm for the above
ReplyDelete