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:

A unsorted sequence s is taken, along with the index numbers where the sequence has to be merged. (p=initial, r = final, q=middle)
Now, left_arr and right_arr are [p,q], [q+1, r] respectively
we take left_arr and right_arr initial values (i=0, j=0). We iterate over the sequence seq...
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)

The homework tag has been deprecated so there's no need to use it anymore (although it's still helpful to mention that it's homework in the text so that people can gauge what answers are most likely to be useful.) — DSM
– DSM, Commented Sep 28, 2012 at 14:34

Ionut Hulub · Accepted Answer · 2012-09-28 15:09:07Z

1

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.

edited Sep 28, 2012 at 15:09

answered Sep 28, 2012 at 14:38

Ionut Hulub

6,3365 gold badges29 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dennis Ritchie Over a year ago

It may not work for all possible values.. it works if we are left with 1 single number in the last iteration..

Dennis Ritchie Over a year ago

[2,4,5,7,6,1,2,3,6] Now, it will be divided into [2,4,5,7,6] and [1,2,3,6]. When right all the right elements are iterated, we are left with [7,6] in left.. in the above code, we are just appending the remaining part, which in this case is not sorted

Ionut Hulub Over a year ago

you have probably forgot to edit the values for p, q and r before calling the merge function. modify q to 4 and r to 8. also, your example won't work because the left array will be [2, 4, 5, 7, 6] and that's not already sorted. merge can only merge to already sorted arrays.

Ashwini Chaudhary · Accepted Answer · 2016-04-26 21:07:41Z

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]

charlee · Accepted Answer · 2012-09-28 14:49:33Z

0

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

answered Sep 28, 2012 at 14:49

charlee

1,3891 gold badge12 silver badges22 bronze badges

Collectives™ on Stack Overflow

Merge Sort Index Error

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related