Index out of range in python for mergesort

Question

I'm working on a project and tried to implement merge sort in python but I'm getting Index out of range Error as I'm new python sp don't know much about python syntax and inbuilt functions

     def merge1(a,l,h):
        if l<h:
            mid=int((l+h)/2)
            left=a[:mid]
            right=a[mid:]
            merge1(left,l,mid)
            merge1(right,mid+1,h)
            mergesort(a,l,mid,h)
     def mergesort(a,l,mid,h):    
        i=l
        j=mid+1
        k=l
        b=[]
        while i<=mid and j<=h:
            if a[i]<=a[j]:
                b[k]=a[i]
                i+=1
            else:
                b[k]=a[j]
                j+=1
            k+=1    
        if i>mid:
            for x in mid(j,h):
                b[k]=a[x]
                k=k+1
        else:
            for x in range(i,mid):
                b[k]=a[x]
                i=i+1
        for i in range(0,k):
            a[k]=b[k]
      a=[9,1,45,99,98,56]
      merge1(a,0,len(a)-1)
      print(a)

    <ipython-input-71-e2786b6fbe02> in mergesort(a, l, mid, h)
     15     b=[]
     16     while i<=mid and j<=h:
---> 17         if a[i]<=a[j]:
     18             b[k]=a[i]
     19             i+=1

    IndexError: list index out of range

Answer 1

Python syntax for sub array is array[begin, end], where the index range is from begin to end-1 inclusive (it doesn't include end). The terminating conditions for indexes should be < not <=, for example i < mid, instead of i <= mid.

The names of merge1 and mergesort are reversed. mergesort() is actually the merge function, and merge1 is actually the top down recursive mergesort function. The names should be swapped.

The merge sort function should only be creating stack of calls that include the array and index range. left and right should be created from the array "a" in the merge function, then merged back into "a" during the merge process.

The initial call to the merge sort function should have parameters (a, 0, len(a))

---

Example code

def mergesort(a,beg,end):
    if (end-beg) > 1:
        mid=(beg+end)//2
        mergesort(a,beg,mid)
        mergesort(a,mid,end)
        merge(a,beg,mid,end)
def merge(a,beg,mid,end):
    left = a[beg:mid]
    right = a[mid:end]
    i = 0
    j = 0
    k = beg   
    while True:
        if left[i] <= right[j]:
            a[k] = left[i]
            i += 1
            k += 1
            if(i < len(left)):
                continue
            a[k:end] = right[j:len(right)]
            break
        else:
            a[k] = right[j]
            j += 1
            k += 1
            if(j < len(right)):
                continue
            a[k:end] = left[i:len(left)]
            break

a=[9,1,45,99,98,56]
mergesort(a,0,len(a))
print(a)