Merge sort doubts

#1

algorithm : https://ide.codingblocks.com/s/209541

as the megre sort first divide array into two and then the recursion takes place and at the end 1-1 element are present.

i am totally confused that how these elements are automatically sorted. as we apply MERGE FUNCTION for TWO sub ARRAYS only.

suppose we have six elements as taken by prateek sir in video. why we are applying merge function to two arrays with 3 elements each. how the single element are sorted which makes two and then three.

my point is that we are applying merge function to two arrays with 3 element each… why?? what about rest. i hope you get my point.

#2

@chaman9,
The 2 subarrays are not sorted “automatically”, rather they are sorted recursively, you can imagine like this, when merge_sort(size=6) is called, it calls two merge_sort(left size=3) and merge_sort(right size=3), which recursively sorts the 2 subarrays.
Like the first left recursive call would be merge_sort(size=3), now this will recursively sort its left and right half, and returned the size=3 array sorted.
Similarly the right recursive call.

It’s hard to write in words, I highly recommend, take a random array and dry run on paper and pen. It will give the best understanding.

#3

how it is recursively sorting (left size=3)
according to my idea mergeSort(arr, s, mid); here we are only spiliting… isnt?
we havnt called any sorting algorithm here

#4

@chaman9,
Did you dry run on a paper and pen, do this, take a random array of size 6, dry run the Algorithms pictorially, and upload a snapshot here. We will see what is the confusion then.

#5

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.

#6

Here is a simple merge sort explanation that was written recently https://www.w3spot.com/2021/03/working-merge-sort-implementation-in.html. It helped me clear my doubts. Posting it here in case someone stumbles onto this old post looking for some kind of explanation.