CODEWITHSUNDEEP
pythonalgorithmrecursionmergesort
Eyeofpie
Eyeofpie

Reputation: 340

Understanding the recursion in mergesort-like algorithms

I was wondering how the flow of this recursive algorithm works: an inversion counter based on merge-sort. When I looked at the diagrams of the merge-sort recursion tree, it seemed fairly lucid; I thought that the leaves would keep splitting until each leaf was a single unit, then merge() would start combining them; and therefore, start 'moving back up' the tree -- so to speak.

But in the code below, if we print out this function with a given array print(sortAndCount(test_case)) then we're actually getting our 'final' output from the merge() function, not the return statement in sortAndCount()? So in the code below, I thought that the sortAndCount() method would call itself over and over in (invCountA, A) = sortAndCount(anArray[:halfN]) until reaching the base case and then moving on to processing the next half of the array -- but now that seems incorrect. Can someone correct my understanding of this recursive flow? (N.b. I truncated some of the code for the merge() method since I'm only interested the recursive process.)

def sortAndCount(anArray):
    N = len(anArray)
    halfN = N // 2

    #base case:
    if N == 1: return (0, anArray)          

    (invCountA, A) = sortAndCount(anArray[:halfN])
    (invCountB, B) = sortAndCount(anArray[halfN:])
    (invCountCross, anArray) = merge(A, B)

    return (invCountA + invCountB + invCountCross, anArray)

def merge(listA, listB):
    counter = 0
    i, j = 0, 0

    #some additional code...
    #...
    #...


    #If all items in one array have been selected, 
    #we just return remaining values from other array:
    if (i == Asize):                                
        return (counter, output_array + listB[j:])
    else:
        return (counter, output_array + listA[i:])

Upvotes: 2

Views: 875

Answers (1)

Padraic Cunningham
Padraic Cunningham

Reputation: 180391

The following image created using rcviz shows the order of recursive call, as explained in the documentation the edges are numbered by the order in which they were traversed by the execution.The edges are colored from black to grey to indicate order of traversal : black edges first, grey edges last.:

enter image description here

So if we follow the steps closely we see that first we traverse the left half of the original array completely then the right.

Upvotes: 3

Related Questions