I wrote a merge sort algorithm and trying to figure out index out of range error. I checked the code in depth but could not see it so I do not have many things to write but I tried to follow the basic process of merge sort algorithm.

def merge(a,lower,middle,upper,b):
  i=lower
  j=middle+1
  k=lower
  while(i<=middle and j<=upper):
    if(a[i]<=a[j]):
      b[k]=a[i]
      i=i+1
    else:
      b[k]=a[j]
      j=j+1
    k=k+1
  if(i>middle):
    while(j<=upper):
      b[k]=a[j]
      j=j+1
      k=k+1
  elif(j>upper):
    while(i<=middle):
      b[k]=a[i]
      i=i+1
      k=k+1
  return b

def mergesort(a,lower,upper):
  if(lower<upper):
    middle=(lower+upper)//2
    mergesort(a,lower,middle)
    mergesort(a,middle+1,upper)
    s=merge(a,lower,middle,upper,[])
  
mergesort([1,3,2,7,11,10],0,5)

I wrote a merge sort algorithm and trying to figure out index out of range error. I checked the code in depth but could not see it so I do not have many things to write but I tried to follow the basic process of merge sort algorithm.

def merge(a,lower,middle,upper,b):
  i=lower
  j=middle+1
  k=lower
  while(i<=middle and j<=upper):
    if(a[i]<=a[j]):
      b[k]=a[i]
      i=i+1
    else:
      b[k]=a[j]
      j=j+1
    k=k+1
  if(i>middle):
    while(j<=upper):
      b[k]=a[j]
      j=j+1
      k=k+1
  elif(j>upper):
    while(i<=middle):
      b[k]=a[i]
      i=i+1
      k=k+1
  return b

def mergesort(a,lower,upper):
  if(lower<upper):
    middle=(lower+upper)//2
    mergesort(a,lower,middle)
    mergesort(a,middle+1,upper)
    s=merge(a,lower,middle,upper,[])
  
mergesort([1,3,2,7,11,10],0,5)

• python
• algorithm

• s=merge(a,lower,middle,upper,[]) - b is empty, so there's no way you can access b[k], whatever the value of k. – Thierry Lathuille Commented Mar 19 at 20:19
• Please read meta.stackoverflow/questions/285551/… to see why we don't accept images of text- and especially bad ones. Textual data must be provided as text. – Thierry Lathuille Commented Mar 19 at 20:21
• what should I have written can not I specify the elements of the empty array like b[0],b[1] etc. – maths and chess Commented Mar 19 at 20:25
• Hello, thank you for your help it worked in colab, I did not know that I should not put any pictures and when I try to put the output of my code from colab stackoverflow automatically thinks that it is code gives error so I can not post my question. What is the exact solution for that? Although code block and output are seperated I could not post so I had to put picture, I did not know it is bad – maths and chess Commented Mar 19 at 21:52

2 Answers 2

The problem is in the value you pass for parameter b, which is an empty list. Any code that tries to assign to b[k] will lead to an index-error, because b doesn't have that index.

One way to solve this, is to use b.append instead of assigning to an index.

Not your question, but you don't do anything with s, so even if you solve the above problem, nothing gets sorted. To get the sorted result in a, you need to copy the sorted partition s back into a.

Finally, the main call doesn't do anything with the sorted result, since you don't have a reference to the list that is passed to mergesort.

Here is a possible correction based on the above comments:

def merge(a,lower,middle,upper,b):
  i=lower
  j=middle+1
  # no more need for variable K, as we use append()
  while(i<=middle and j<=upper):
    if(a[i]<=a[j]):
      b.append(a[i]) # use append, here and below
      i=i+1
    else:
      b.append(a[j])
      j=j+1
  if(i>middle):
    while(j<=upper):
      b.append(a[j])
      j=j+1
  elif(j>upper):
    while(i<=middle):
      b.append(a[i])
      i=i+1
  return b
  
def mergesort(a,lower,upper):
  if(lower<upper):
    middle=(lower+upper)//2
    mergesort(a,lower,middle)
    mergesort(a,middle+1,upper)
    # copy the sorted result back into A:
    a[lower:upper+1]=merge(a,lower,middle,upper,[])

a = [1,3,2,7,11,10]  # get a reference to the input
mergesort(a,0,len(a)-1)
print(a)  # ... so that you can use the result afterwards

Not a complete answer, but I want to expand on something that @trincot said.

You asked,

What should I have written? Can not I specify the elements of the empty array like b[0],b[1] etc.?

And trincot said,

The problem is in the value you pass for parameter b, which is an empty list. Any code that tries to assign to b[k] will lead to an index-error, because b doesn't have that index.

Python does not have arrays. Python only has lists, which can be used like arrays, but they're not exactly the same. In particular, this expression [] creates an empty list. That is, a list with no elements. You cannot specify any element of an empty list because there are no elements there to be specified.

Trincot suggested that you can append members to the empty list. But if your algorithm really wanted an array, there is another way. This expression creates a new list with n members that are all equal to e:

[e]*n

So, for example, if you happened to have a list, a, that you're using like an array, and you want to call merge, passing in another array-like list that is the same length as a, you could do this:

s=merge(a,lower,middle,upper,[0]*len(a))

The last arg in the merge call will be a list, with the same length as the list, a, but whose members are all zero. Inside the merge function, you will then be able to use the argument, b, as if it was an array, and you'll be able to overwrite its members with values from the a list. That is to say, lines like this will no longer give you errors:

b[k]=a[j]

But note! That will only get you part way to a working solution. Your code still has other problems which, if you can't figure them out on your own, probably should be asked here as new questions rather than complicating this question and its answers.