Can anyone please help me in understanding the following python code

[rusi]

On May 30, 2:48 pm, bhk... at gmail.com wrote:
> Code :
> -----
> def mergeSort(alist):
>     print("Splitting ",alist)
>     if len(alist)>1:
>         mid = len(alist)//2
>         lefthalf = alist[:mid]
>         righthalf = alist[mid:]
>
>         mergeSort(lefthalf)
>         mergeSort(righthalf)
>
>         i=0
>         j=0
>         k=0
>         while i<len(lefthalf) and j<len(righthalf):
>             if lefthalf[i]<righthalf[j]:
>                 alist[k]=lefthalf[i]
>                 i=i+1
>             else:
>                 alist[k]=righthalf[j]
>                 j=j+1
>             k=k+1
>
>         while i<len(lefthalf):
>             alist[k]=lefthalf[i]
>             i=i+1
>             k=k+1
>
>         while j<len(righthalf):
>             alist[k]=righthalf[j]
>             j=j+1
>             k=k+1
>     print("Merging ",alist)
>
> alist = [54,26,93,17,77,31,44,55,20]
> mergeSort(alist)
> print(alist)
>
> Output:
> -------
> ('Splitting ', [54, 26, 93, 17, 77, 31, 44, 55, 20])
> ('Splitting ', [54, 26, 93, 17])
> ('Splitting ', [54, 26])
> ('Splitting ', [54])
> ('Merging ', [54])
> ('Splitting ', [26])
> ('Merging ', [26])
> ('Merging ', [26, 54])
> ('Splitting ', [93, 17])
> ('Splitting ', [93])
> ('Merging ', [93])
> ('Splitting ', [17])
> ('Merging ', [17])
> ('Merging ', [17, 93])
> ('Merging ', [17, 26, 54, 93])
> ('Splitting ', [77, 31, 44, 55, 20])
> ('Splitting ', [77, 31])
> ('Splitting ', [77])
> ('Merging ', [77])
> ('Splitting ', [31])
> ('Merging ', [31])
> ('Merging ', [31, 77])
> ('Splitting ', [44, 55, 20])
> ('Splitting ', [44])
> ('Merging ', [44])
> ('Splitting ', [55, 20])
> ('Splitting ', [55])
> ('Merging ', [55])
> ('Splitting ', [20])
> ('Merging ', [20])
> ('Merging ', [20, 55])
> ('Merging ', [20, 44, 55])
> ('Merging ', [20, 31, 44, 55, 77])
> ('Merging ', [17, 20, 26, 31, 44, 54, 55, 77, 93])
> [17, 20, 26, 31, 44, 54, 55, 77, 93]
>
> 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.
>
> Can anyone please help me out here?

Not in direct answer to your question... Still see if this helps you
to understand mergesorting better.

I generally find that mixing recursion along with imperative
programming makes recursion look difficult.
Imperative programming goes scot-free and recursion gets a bad name!!

So here is a pure recursive/functional solution.  Tell me if you
understand it better (or worse!!)
Its written to demonstrate the IDEA of mergesort. Its actual
efficiency is sub-par for various reasons.

-------------------------------------
# merging two lists, both assumed sorted
def merge(a,b):
    if a == []: return b
    elif b== []: return a
    elif a[0] < b[0]:
        return [a[0]] + merge(a[1:],b)
    else:
        return [b[0]] + merge(a,b[1:])

# The same as merge above written in pure functional style
def merge1(a,b):
    return (b if a == [] else
            a if b == [] else
            [a[0]] + merge(a[1:],b) if a[0] < b[0] else
            [b[0]] + merge(a,b[1:])
           )

def mergeSort(alist):
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]
        return merge1(mergeSort(lefthalf),mergeSort(righthalf) )
    else:
        return alist