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?
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 . When you call arr.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.