0
$\begingroup$

I have the following diagram showing a case of merge sort:

enter image description here

I am trying to find the value that would be in the box with the red cross when applying merge sort in ascending order.

It seems to me that it would be $71$. If we start at the bottom-right, we have $[30, 71]$ for the first array. We then have the sorted arrays $[24, 30, 71]$ and $[49, 97]$. And then we combine these last two sorted arrays to get $[24, 30, 49, 71, 97]$. Therefore, the value in the box with the red cross would be $71$, right? And does it matter whether we start at the bottom-left or bottom-right? The result should be the same, right?

$\endgroup$

1 Answer 1

1
$\begingroup$

You don't need to simulate merge sort to figure out what that value will be. Since you know that mergesort is correct, and you're looking for the 4-th element in that subarray, you just need to find the element with rank $4$ among $\{71, 30, 24, 49, 97\}$, i.e., $71$.

This value is independent of the order in which you choose to execute the recursive calls (as long as you execute all the child calls before the parent one).

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. So whether I start merging at the bottom-left or bottom-right doesn't matter? $\endgroup$ Oct 22, 2022 at 15:06
  • $\begingroup$ Correct.$\phantom{}$ $\endgroup$
    – Steven
    Oct 22, 2022 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.