In this question, I have given the python code for a mergeSort algorithm. Hereby, the merge_sort2() function is a recursive function.
Now, I am trying to understand the callflow of this function: Say we are given a list with 8 entries, such as
[17, 87, 6, 22, 41, 3, 13, 54]
It will be split like this:
[17, 87, 6, 22] [41, 3, 13, 54]
[17, 87] [6, 22] [41, 3] [13, 54]
[17] [87] [6] [22] [41] [3] [13] [54]
So. I think, internally, sth like this will happen:
middle = (0 + 7) // 2 # = 3
merge_sort2(x, 0, 3)
middle = (0 + 3) // 2 # = 1
merge_sort2(x, 0, 1)
middle = (0 + 1) // 2 # = 0
merge_sort2(x, 0, 0) #does nothing
merge_sort2(x, 1, 1) #does nothing
merge(x, 0, 0, 1)
merge_sort2(x, 2, 3)
middle = (2 + 3) // 2 # = 2
merge_sort2(x, 2, 2) #does nothing
merge_sort2(x, 3, 3) #does nothing
merge(x, 2, 2, 3)
merge(x, 0, 1, 3)
merge_sort2(x, 4, 7)
...
merge(x, 0, 4, 7)
yeah. Somewhat like this. I guess I am having troubles understanding recursion. But does this look right?
