# Issue

This Content is from Stack Overflow. Question asked by user366018

This is my first merge sort implementation with Python.

``````unsorted_list = [7, 4, 2, 1]

def merge(left_array, right_array):
lst = []

# compare the element in both array
i = 0
while len(left_array) > 0 and len(right_array) > 0:
if left_array[i] <= right_array[i]:
lst.append(left_array[i])
del left_array[i]
i += 1
else:
lst.append(right_array[i])
del right_array[i]
i += 1

# append the rest if one of the array is empty
if len(left_array) > 0:
for j in left_array:
lst.append(j)

if len(right_array) > 0:
for h in right_array:
lst.append(h)

# return the sorted sub-list
return lst

def merge_sort(array):
# return the array if there is only 1 element
if len(array) <= 1:
return array

# divide the array in 2 halves
mid = (len(array))//2
left = array[:mid]
right = array[mid:]

# recursion
merge_sort(right)
merge_sort(left)
return merge(left, right)

print(merge_sort(unsorted_list))
``````

But the console showed this error instead of a sorted list:

`````` File "c:Users...merge_sort.py", line 64, in <module>
print(merge_sort(unsorted_list))
File "c:Users...merge_sort.py", line 62, in merge_sort
return merge(left, right)
File "c:Users...merge_sort.py", line 28, in merge
if left_array[i] <= right_array[i]:
IndexError: list index out of range
``````

I expect the result should be this or somthing like that:

``````[1, 2, 4, 7]
``````

As i goes from 0 and it stop adding if one array i.e. right_array & left_array goes empty, i should not be greater than the largest index of the array.

I dont know how to solve my error. how to correct it?

# Solution

Remove the 2 lines where i+=1. and replace i with 0.

In your current code while you deleting num from list you increment i by 1. Then actualy miss some numbers in in both left and right arrays.

Ex: in a list(variable name as arr) have 2 number as follows[1,2]. If you delete 1 then new list is [2]. When you call arr[1].Now it return indexError because now there is no 2 nums in list.

``` This Question was asked in  StackOverflow by  user366018 and Answered by YJR It is licensed under the terms of
CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.```