CLRS Chapter 2.3.1 Merge Sort Implementation in Python

After reading this chapter, I would love to get my hand dirty and work out the mergesort in python. It ended up taking me almost and hour to implement this algorithm. There are several things that caught me unguarded.

• np.floor cannot be used in this case as it returns a float number which cannot be used in the range function.
• range function is inclusive on the left not the right. so range(1,4) gives you [1,2,3].
• Indexing also messes things up. Pay attention to the indexing. I find indexing starting from 1 to be more natural for the function argument.

import numpy as np
def merge(A,p,q,r):
    L = [A[i] for i in range(p-1,q)
    R = [A[i] for i in range(q,r)]
    #Add in sentinel
    L.append(np.inf)
    R.append(np.inf)
    for i in range(p-1,r):
        if L[0] < R[0]:
            A[i] = L[0]
            L.pop(0)
        else:
            A[i] = R[0]
            R.pop(0)
            
def mergesort(A,p,r):
    if p < r:
        q = (p+r)/2
        print q
        mergesort(A,p,q)
        mergesort(A,q+1,r)
        merge(A,p,q,r)

z = [0,3,2,1,4,5,8]
mergesort(z,1,len(z))
z