Merge sort using Recrsion

#21 
MergeSort(A, s, e):
if s > =e 
    return
mid = (s+e)/2
mergeSort(A, s, mid)              <---- this recursively sort first array ie [s.....mid]
mergeSort(A, mid+1, e)         <---- this recursively sort second array ie [mid+1....e]
merge(A, s, mid, e)    <-- ------ this is where we are calling merge function to merge the two already sorted array ( [s....mid] and [mid+1 ......e])
#22

hi @jatinupadhyay786 i’d suggest you to do a dry run on the array if you are having so much coonfusion.

This ought to help.
Now please tell what exactly is your confusion with as I am unable to get it.

#23

still mot able to figure out how merge is getting called using recursion i understand the code inside it but the problem is when i dry run it i cant figure out how its is getting called

#24

@jatinupadhyay786

we pass the array and change the indices i, and j for recursive calls to pass around different parts of the array. We do so by the statement merge(A, s, mid) and merge(A, mid+1, e)

In the base case, when there is 1 element, we do nothing because that array is already sorted. Now suppose there are 2 elements. That array can be divided into 2 parts {0} {1}, we merge these 2 subarrays into a single subarray such that the bigger subarray is now sorted. Again, we repeat the process with subarrays of bigger sizes and keep doing so until the whole array is sorted.

#25

sorry but its still not clear to me

#26

@jatinupadhyay786 please clear your basics of recursion and then try to understand it.

#27

i have cleared it but i am getting stuck at only one point when i dry run it using the code that i wrote

#28

and the thing is i cant even upload my screenshot of the code where i did it

#29

@jatinupadhyay786 you can upload a picture, there is an option to do so. Please tell where you are stuck in dry run part. This is the link of your doubt thread, Merge sort using Recrsion if you open it directly you can see an option to upload images.

#30

i am not able to find the option of upload

#31

@jatinupadhyay786 image it is this icon

#32

is it on the thread or where??

#33

@jatinupadhyay786 it is in top bar of the reply box. Reply box appears at the very bottom of the thread.