merge sort in place report index out of range error

Question

I mimic from the answer https://stackoverflow.com/a/19086076/10892923 of an inplace merge sort as

import unittest
import logging

logging.basicConfig(level=logging.DEBUG, format="%(levelname)s　%(message)s")

#in-place merge sort
def merge_inplace(A, start, mid, end) -> "None":
    left = A[start:mid]
    right = A[mid:end]
    i = 0
    j = 0

    for c in range(start,end): #c for cur
        if (i < len(left) and left[i] <= right[j]) or i >= len(right):
            A[c] = left[i]
            i = i + 1
        else:
            A[c] = right[j]
            j = j + 1

def mergeSort_inplace(A, lo, hi) -> "None":
    if lo < hi - 1:
        mid = (lo + hi) // 2
        mergeSort_inplace(A,lo,mid)
        mergeSort_inplace(A,mid,hi)
        merge_inplace(A, lo, mid, hi)

class MyCase(unittest.TestCase):
    def test_a(self):
        A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
        mergeSort_inplace(A,0,len(A))
        print(A)

unittest.main()

I double checked the logic and assert that it very clear,
it reported error otherwise.

ERROR: test_a (__main__.MyCase)
----------------------------------------------------------------------
Traceback (most recent call last):                                                                               
  File "mergeSort.py", line 31, in test_a                                                                        
    mergeSort_inplace(A,0,len(A))                                                                                
  File "mergeSort.py", line 24, in mergeSort_inplace                                                             
    mergeSort_inplace(A,lo,mid)                                                                                  
  File "mergeSort.py", line 24, in mergeSort_inplace                                                             
    mergeSort_inplace(A,lo,mid)                                                                                  
  File "mergeSort.py", line 26, in mergeSort_inplace                                                             
    merge_inplace(A, lo, mid, hi)                                                                                
  File "mergeSort.py", line 15, in merge_inplace                                                                 
    A[c] = left[i]                                                                                               
IndexError: list index out of range                                                                              

----------------------------------------------------------------------                                           
Ran 1 test in 0.000s                                                                                             

FAILED (errors=1)

I cannot locate the error why it report list index out of range.

score 1 · Accepted Answer · answered May 26 '19 at 10:19

You encountered a short-circuit problem,

Change

 if (i < len(left) and left[i] <= right[j]) or j >= len(right):

to

if j >= len(right) or (i < len(left) and left[i] <= right[j]):

More details please refer to python - Bug with logic operator "or"? - Stack Overflow
and Built-in Types — Python 3.7.3 documentation

merge sort in place report index out of range error

1 Answers1