Problems with the pseudocode in CLRS

Question

I'm using CLRS as an introduction to algorithms. I am trying to implement the algorithm written in pseudocode in the book, in Python. However, i'm having problems because the book starts indexing from 1. This is how I implemented Merge Sort, but it doesn't work correctly:

def MergeSort(A, start, end):
    if(start < end):
        middle = math.floor((start + end)/2)
        MergeSort(A, start, middle)
        MergeSort(A, middle + 1, end)
        Merge(A, start, middle, end)

def Merge(A, start, middle, end):
    n1 = middle - start + 1
    n2 = end - middle
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[start + i - 1]
    for j in range(0, n2):
        R[j] = A[middle + j]
    i = 0
    j = 0
    for k in range(start, end):
        if(i >= n1):
            A[k] = R[j]
            j += 1
        elif(j >= n2):
             A[k] = L[i]
             i += 1
        elif(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

How should I convert from pseudocode to Python code without having these (off-by-one?) errors ?

Answer 1

There is a Small error it is easy to over look this , indices in line of your merge function

A[start + i - 1] should be start + i

Because you begin looping i from 0 and value of start can also get 0 which makes it start + i -1
and for the iteration where

start == i == 0

your index becomes -1 which is actually the last element of your list in Python

and in final loop of your merge function The range should be

for k in range(start, end+1) because it has to be iterated from start up until end inclusive

This should run fine

import math
def MergeSort(A, start, end):
    if(start < end):
        middle = math.floor((start + end)/2)
        MergeSort(A, start, middle)
        MergeSort(A, middle + 1, end)
        Merge(A, start, middle, end)

def Merge(A, start, middle, end):
    n1 = middle - start + 1
    n2 = end - middle
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = A[start + i ]
    for j in range(0, n2):
        R[j] = A[middle + j+1]
    i = 0
    j = 0
    for k in range(start, end+1):
        if(i >= n1):
            A[k] = R[j]
            j += 1
        elif(j >= n2):
             A[k] = L[i]
             i += 1
        elif(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


arr=[4,8,5,6,9,8,1]
MergeSort(arr,0,len(arr)-1)
print(arr)