 MRGSRT - EDITORIAL

**Difficulty:**Medium

Pre-requisites: Divide and conquer

Problem: To find the stack image when merge sort is called.

Explanation:

This problem can be solved in two ways:

1. By simulating merge sort and printng

2. Using binary search:

In this approach the given size is divided into 2 parts using

``````mid=(L+R)/2;
if(mid>=N)		//N is the index to be found
R=mid;		//Shift the right pointer to middle i.e. index lies between middle and left
else
L=mid+1;	//Shift the left pointer to middle+1 i.e. index lies between middle and right
``````

Using the second one is more preferable.

Problem setter’s solution: SOLUTION

I am unable to understand what is the problem statement. Can anyone elaborate the question(problem statement)?

Problem: To find the stack image when `mergesort(A,i,i)` is called from the driver function.
As explained in the editorial, there are 2 ways of solving the problem.

1. You can simulate the `mergesort(A,start,end)` function when it is called from the driver function which in `C/C++` is `main()` function.
2. You can use binary search for the index `i`.
Time Complexity: `O(log (s-t))`.