Suppose an unsorted array with the following contents is to

Suppose an unsorted array with the following contents is to be sorted by Mergesort:

3 4 8 1 5 4 6 10

Just before the final merge, what will the value at the beginning of the first half-array be?

Just before the final merge, what will the value at the beginning of the second half-array be?

Solution

Mergesort works on the principle that divide the given array into two half arrays , sort each array repeatedly sort each half and then merge both halves together.

Thus two arrays from given arrays are as follows :

A1=[3 ,4,8,1] and A2 = [5,4,6,10]

Now we again divide each array into two halves as

A1_a =[3,4], A1_b=[8,1],A2_a=[5,4],A2_b=[6,10]

Now we merge each array by comparing them, so that these four arrays change as :

A1_a =[3,4], A1_b=[1,8],A2_a=[4,5],A2_b=[6,10]

Now we again repeat the same process of comparing and merging in two arrays of left side array so that last merged left half array will be A1=[1,3,4,8] so just before the final merge, 1 will be the value at the beginning of the firt half array.

This is first answer.

And clearly as second array is already in sort form there, so 4 will remain the required first value of this second half array, just before final merge.

This is second answer.