Merge Sort Index Error

Question

def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = [] 
    right_arr = []
    for i in xrange(0, n1):
        left_arr.append( seq[p+i] )
    for j in xrange(0, n2):
        right_arr.append( seq[q+j+1] )

    j=0
    i=0
    for k in xrange(p,r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
        else:
            seq[k]=right_arr[j]
            j+=1
    return seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

How it works:

1. A unsorted sequence s is taken, along with the index numbers where the sequence has to be merged. (p=initial, r = final, q=middle)

2. Now, left_arr and right_arr are [p,q], [q+1, r] respectively

3. we take left_arr and right_arr initial values (i=0, j=0). We iterate over the sequence seq...

4. while iterating we are replacing the values of seq with the sorted values...

The above function is able to sort till last number "7".. at the end, its showing "IndexError". I can use exception handling to catch it and fix but I think... for merge sort, its too much.. Can anyone help me in fixing the code as easy as possible.

I am learning Algorithms.. (following book: Introduction to Algorithms by Thomas H. Cormen)

Answer 1

The problem with your code is that you're looping over xrange(p, r+1), so during that loop in some iteration the value of either i or j might become equal the value of len(left) or len(right), causing the IndexError eventually.

def merge(seq,p,q,r):
    left=seq[p:q+1]       #a better way to fetch the list
    right=seq[q+1:]       
    i=0
    j=0
    #you shuldn't loop over the length of seq as that might make the value of either i or j
    # greater than the length of left or right lists respectively.
    # so you should only loop until one of the lists is fully exhausted

    while i<len(left) and j<len(right):
        if left[i] <= right[j] :
            seq[i+j]=left[i]
            i+=1
        else:
            seq[i+j]=right[j]
            j+=1

    #now the while loop is over so either right or left is fully traversed, which can be
    #find out my matching the value of j and i with lenghts of right and left lists respectively

    if j == len(right):
        seq[i+j:]=left[i:]  #if right is fully traversed then paste the remaining left list into seq
    elif i==len(left):      #this is just vice-versa of the above step
        seq[i+j:]=right[j:] 
    print seq

s = [2,4,5,7,1,2,3,6]
p = 0
q = 3
r = 7
merge(s,p,q,r)

output:

[1, 2, 2, 3, 4, 5, 6, 7]

Answer 2

the problem is that at the last iteration i will be equal to 4 and you are trying to access left_arr[5] which does not exist. you should add a stopping condition when i or j become larger then the size of the corresponding array, and then add all the remaining elements in the other array to seq.

Here is a code that works:

def merge (seq, p, q, r):
    # n1: length of sub-array [p..q]
    n1 = q - p + 1
    # n2: length of sub-array [q+1 ..r]
    n2 = r - q
    # Left and Right arrays
    left_arr = seq[p:n1] #here 
    right_arr = seq[n1:r+1]  #here
    j=0
    i=0
    for k in xrange(p, r+1):
        if left_arr[i]<= right_arr[j]:
            seq[k]=left_arr[i]
            i+=1
            if i > n1-1: #here
                break
        else:
            seq[k]=right_arr[j] #here
            j+=1
            if j > n2-1:
                break
    if i >= len(left_arr): #from here down
        seq[k+1:] = right_arr[j:]
    elif j >= len(right_arr):
        seq[k+1:] = left_arr[i:]

    return seq

s = [2,4,5,7,1,1,1,1]
p = 0
q = 3
r = 7
print merge(s,p,q,r)

I have marked with comments the places where I have edited your code.

Answer 3

You didn't check the array index while iterating left_arr and right_arr. You should merge the left part of either array when another array ends.

for k in xrange(p,r+1):
    if left_arr[i]<= right_arr[j]:
        seq[k]=left_arr[i]
        i+=1
    else:
        seq[k]=right_arr[j]
        j+=1

    # --------------- add this ----------------
    # if any array ends, merge the left elements of the other array
    if i >= len(left_arr):
        seq[k:] = right_arr[j:]
        break
    elif j >= len(right_arr):
        seq[k:] = left_arr[i:]
        break
    # --------------- end ----------------
return seq