Can anyone please help me in understanding the following python code

[Joshua Landau]

On 30 May 2013 10:48,  <bhk755 at gmail.com> wrote:
> Question:
> ---------
> Function mergeSort is called only once, but it is getting recursively executed after the printing the last statement "print("Merging ",alist)". But don't recursion taking place except at these places "mergeSort(lefthalf), mergeSort(righthalf)"
>
> Sometimes the function execution directly starts from i=0,j=0,k=0 . Not sure how.

Here's some different code; it does the same thing but in a less weird way:

##########################
def mergeSort(alist, depth=1):
    # If the piece we have to sort is [i] or [], then we have no sorting to do
    if len(alist) <= 1:
        # Returning what we were given
        # Make a new list from it, though, because we are nice
        print("{padding}return {list}\n".format(padding=" "*depth*8,
list=alist))
        return alist[:]

    # Split along the middle
    mid = len(alist)//2

    # We have two halves
    lefthalf = alist[:mid]
    righthalf = alist[mid:]

    # Which we sort, so we have two sorted halves
    print("{padding}lefthalf  = mergesort({list})\n".format(padding="
"*depth*8, list=lefthalf))
    lefthalf  = mergeSort(lefthalf,  depth+1)

    print("{padding}righthalf = mergesort({list})\n".format(padding="
"*depth*8, list=righthalf))
    righthalf = mergeSort(righthalf, depth+1)


    # We want to return a sorted "alist" from our two lists
    # We'll add the items to here
    new_list = []

    # We'll go through adding the smallest to new_list
    while lefthalf and righthalf:

        # Lefthalf has the smaller item, so we "pop" it off into new_list
        if lefthalf[0] < righthalf[0]:
            new_list.append(lefthalf.pop(0))

        # Righthalf has the smaller item, so we "pop" it off into new_list
        else:
            new_list.append(righthalf.pop(0))

    # One of our lists isn't empty, so just add them on
    new_list += lefthalf + righthalf

    print("{padding}return {list}\n".format(padding=" "*depth*8, list=new_list))
    return new_list

print("Start mergesort({list}):\n".format(list=[2, 4, 0, 1]))

sorted_list = mergeSort([2, 4, 0, 1])

print("Our final result: {list}".format(list=sorted_list))
##########################

And it gives

##########################
Start mergesort([2, 4, 0, 1]):

        lefthalf  = mergesort([2, 4])

                lefthalf  = mergesort([2])

                        return [2]

                righthalf = mergesort([4])

                        return [4]

                return [2, 4]

        righthalf = mergesort([0, 1])

                lefthalf  = mergesort([0])

                        return [0]

                righthalf = mergesort([1])

                        return [1]

                return [0, 1]

        return [0, 1, 2, 4]

Our final result: [0, 1, 2, 4]
##########################

Hopefully this code is a little easier to understand - the original
changes the list while it is running the algorithm and mine makes new
lists. The algorithm is very similar, and what you learn applies to
both.

You can see in the output (thanks Chris Angelico) that the main
function is always running. It runs *two* other instances: lefthalf
and righthalf.

So the "mergesort([2, 4, 0, 1])" runs "lefthalf  = mergesort([2, 4])"

"mergesort([2, 4])" runs "lefthalf  = mergesort([2])"

"mergesort([2])" gives back [2] to "mergesort([2, 4])"

"mergesort([2, 4])" goes "OH! I can continue now" and runs "righthalf
= mergesort([4])"

"mergesort([4])" gives back [4] to "mergesort([2, 4])"

"mergesort([2, 4])" goes "OH! I can continue now" and gives back [2,
4] to "mergesort([2, 4, 0, 1])"

"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and runs
"righthalf = mergesort([0, 1])"

"mergesort([0, 1])" runs "lefthalf  = mergesort([0])"

"mergesort([0])" gives back [0] to "mergesort([0, 1])"

"mergesort([0, 1])" goes "OH! I can continue now" and runs "righthalf
= mergesort([1])"

"mergesort([1])" gives back [1] to "mergesort([0, 1])"

"mergesort([0, 1])" goes "OH! I can continue now" and gives back [0,
1] to "mergesort([2, 4, 0, 1])"

"mergesort([2, 4, 0, 1])" goes "OH! I can continue now" and gives back
[0, 1, 2, 4]

DONE.

Does that help you see the flow?



Exactly the same flow happens for your code. The difference is that
instead of returning a list, mergesort *sorts* a list, and then that
is used to replace items in the original list. Personally, their way
is a little silly (and mine is inefficient, so use neither).


Question: Why did you rewrite the code?
Answer: Revising is boring.


Question: Sometimes the function execution directly starts from
i=0,j=0,k=0 . Not sure how.
Answer: That's not a question. Anyhow:

i, j and k are LOCAL to a function. "mergesort([2, 4, 0, 1])" has a
different i, j and k than "mergesort([0, 1])", They never use each
other's i, j and k. Hence for each recursion they run "i=0, j=0, k=0"
and they are set to 0 within the function.


Does this help?