Python MergeSort

Question

I am trying to implement a Python merge sort, But I am failing in some points. the pseudo code I have is accurate but looks like it was built for a different language.

The pseudo requires the following
/declare array temp of size of input array a

I am not sure how this is possible in Python. Anyway, the code is below. The whole idea is that I need to sort the array/list and return the sorted one.

As of now, it's failing with the following message. I would say that this is because of the new temp array/list, but I am not sure

Traceback (most recent call last):  
  File "./mergesort", line 56, in <module>  
    main()  
  File "./mergesort", line 52, in main  
    mergesortbase(array)  
  File "./mergesort", line 4, in mergesortbase  
    mergesort(num, 0, len(num)-1)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 10, in mergesort  
    mergesort(num, low, mid)  
  File "./mergesort", line 12, in mergesort  
    merge(num, low, mid, mid+1, high)  
  File "./mergesort", line 27, in merge  
    temp[k] = a[j]  
IndexError: list assignment index out of range  

Note: a total revamp of the code is not helping, as I will need to use that exact pseudo code.

#!/usr/bin/python3.6

def mergesortbase(num):
    mergesort(num, 0, len(num)-1)


def mergesort(num, low, high):
    if low < high:
      mid = (low + high) // 2
      mergesort(num, low, mid)
      mergesort(num, mid+1, high)
      merge(num, low, mid, mid+1, high)

def merge(a, l1, u1, l2, u2):
# declare array temp of size of input array a
# Comment -- Not doable in Python to create array/list with specific size
    temp = []
    i = l1
    j = l2
    k = l1

    while (i <= u1 and j <= u2):
      if (a[i] <= a[j]):
         temp[k] = a[i]
         i = i + 1
      else:
         temp[k] = a[j]
         j = j + 1

      k = k + 1

    while ( i <= u2 ):
       temp[k] = a[i]
       k = k + 1
       i = i + 1

    while ( j <= u2 ):
       temp[k] = a[j]
       k = k + 1
       i = i + 1

    h = l1

    while ( h <= u2 ):
       a[h] = temp[h]
       h = h + 1


def main():
   array = [8, 5, 7, 1, 9, 3]
   mergesortbase(array)


if __name__ == "__main__":
  main()

Answer 1

Three errors in your code

1. temp is not initialized to any size so k always give list assignment index out of range

2. Second while loop for adding the remaining elements l1 to u1 needs to run only till u1 not u2:

3. Third while loop for adding the remaining elements from l2 to u2 need to increment j rather than i.

   def merge(a, l1, u1, l2, u2):
       temp = [0]*len(a)
       i = l1
       j = l2
       k = l1
       while (i <= u1 and j <= u2):
           if (a[i] <= a[j]):
               temp[k] = a[i]
               i = i + 1
           else:
               temp[k] = a[j]
               j = j + 1
   
           k = k + 1
       while ( i <= u1 ):
           temp[k] = a[i]
           k = k + 1
           i = i + 1
       while ( j <= u2 ):
           temp[k] = a[j]
           k = k + 1
           j = j + 1
   
       h = l1
   
       while ( h <= u2 ):  
           a[h] = temp[h]
           h = h + 1