In the merge sort code the goes as follows
mergesort(b,s,mid);
mergersort(c,mid+1,e);
merge(it merges two arrays)
now as system starts compiling then first mergesort(b,s,mid); comes first so it will divide the array,till the array contains single elements so my doubt is whether it will first sort and merge the broken array or break down the other half of the main array
Hello @vijayraghav18,
Hello @vijayraghav18,
It will first sort the first half and will then sort the second half and will then combine the two.
So, an array of 0 or 1 element is already sorted so, it will return and then go for the second half and will divide and sort it and will combine(sort) the current two halfs.
Suggestion:
Try to draw a tree like structure to understand the flow of the code.
Hope, this would help.’
Give a like if you are satisfied.
But according to the code first the left array will be completely divided and then the right array will be completely divided and then the array will be sorted
As the compiling of code goes line by line therefore first the left part of the array splits then right part of the array splits and then we merge the arrays but in video they told that right part of the array splits and then merged using merge function then left part of the array splits and then get merged
Hello @vijayraghav18,
Yes, that’s exactly what would happen.
And that’s what i have explained.
Let’s understand with an example:
1: refers to the initial unsorted array.
At each step it will break into two half:
____________ 1
______2 __________3
___4 ______5 __6 ______7
Explanation:
Top Down Movement:
First 1 will break into two halves 2 and 3.
Then 2 will break into 4 and 5
Bottom Up Movement:
as 4 is containing a single element, so we will return.
Now, going to right half, 5 is also a single element array. So, return.
Now, merge 4 and 5 and return.
So, two is now sorted.
Above was the left half of 1 which is sorted now.
Now, we will go to the right half.
3 will break into 6 and 7 and the similar pattern will follow.
Observation:
For each node as the current node,
first left half will be sorted
then right half
Finally we will merge the two in sorted order.
Hope, it is clear now.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.