CODEWITHSUNDEEP
algorithmsortingrecursion
Heroe__
Heroe__

Reputation: 274

How does the merge sort algorithm go "up the tree"?

I'm having trouble understanding how the recursive merge sort algorithm works, I understand how it theoretically works : if there's more than one element in an array find its middle and divide the array into 2 smaller sub-arrays and so on until you have 2 arrays of 1 element that are by definition already sorted (base case) then you can merge them using a merging algorithm, then you go up the tree and so on.

I've tried to implement it in python with some print statements to follow step by step and it works but I don't really understand why it works the way it does. I'll describe you my wrong logic:

the algorithm in pseudo code with l being the low index and h the high index :

merge_sort(l,h){

if(l < h){
mid = (l+h)//2
merge_sort(l,mid) 
merge_sort(mid+1,h)
merge(l,mid,h)
}

}

so for a an arr = [9,3,7,5]

from here l == h so we don't fulfill the condition l < h and thus merge_sort doesn't call itself again, for me the algorithm ends here ( which is obviously wrong ) BUT here it goes upand calls merge_sort(1,1) [3] (right side of the array) then merge is executed. After that it goes up again and tackles the right side of the initial array merge_sort(2,3) [7,5] and continues. ( [7] then [5] then merging )

Can someone please explain me why the algorithms continues to call himself after l == n ? I've read some explanations and watch some videos and some even argues merge(l,mid) sort the full first half [9,3] and merge(mid+1,h) sort the second full half [7,5] which is apparently not how it's working, I'm really confused.

Upvotes: 0

Views: 493

Answers (3)

user22037378
user22037378

Reputation: 1

You can read this article, it provides clear explanation: https://medium.com/@ruchi961/a-complete-step-by-step-visual-tutorial-to-merge-sort-with-implementation-in-python-f7beff7f7e54

After the l<h condition fails i.e. it is false it returns back to the calling line. the function which called it and recursivley back returning.

Upvotes: 0

user1196549
user1196549

Reputation:

You can understand a recursive algorithm by trusting it. Have a look at the annotation below (! starts a comment):

merge_sort(l,h) {

if (l < h) {
    mid = (l+h)//2
    merge_sort(l,mid) ! If merge_sort does its job, the array is now sorted from l to mid
    merge_sort(mid+1,h) ! If merge_sort does its job, the array is now sorted from mid+1 to h
    merge(l,mid,h) ! If merge does its job, the array is now sorted from l to h
}
else { ! If l==h, the array is already sorted from l to h
}

Now you can see that if we call the function with some values of l and h, it will return a sorted array, by calling itself on parts of the array, each time returning them sorted. The whole construction works because the size of the subarrays goes decreasing across the levels of calls, and always reaches 1, causing an immediate return to the calling level.

Upvotes: 1

S.Ptr
S.Ptr

Reputation: 122

It doesn't call itself again, it returns back to it's previous step in recursion, once it finishes the current one.

Here is an example from GeeksForGeeks of a merge sort algorithm, with each step labeled numerically in a sequential order: merge sort algorithm, with each step labeled numerically in a sequential order

Upvotes: 3

Related Questions