I'm trying to recreate the merge sorting algorithm and while my code works for lists with length 4 or less when the length gets bigger it crushes.
As you'll see the error says that on some point sorted_right becomes NoneType. I tried debugging it but couldn't understand why this happens. Can anyone help me with this?
My code:
my_list = [5, 35, 10, 1, 0]
def merge_sort(array):
if len(array) == 1:
return array
elif len(array) == 2:
if array[0] > array[1]:
array[0], array[1] = array[1], array[0]
return array
else:
sorted_part = []
left = array[:len(array)//2]
right = array[len(array)//2:]
sorted_left = merge_sort(left)
sorted_right = merge_sort(right)
for i in range(len(array)):
if len(sorted_left) == 0:
sorted_part.extend(sorted_right)
break
elif len(sorted_right) == 0:
sorted_part.extend(sorted_left)
break
else:
if sorted_left[0] < sorted_right[0]:
sorted_part.append(sorted_left.pop(0))
else:
sorted_part.append(sorted_right.pop(0))
print(sorted_part)
merge_sort(my_list)
The error:
[0, 1, 10]
Traceback (most recent call last):
File "C:\Users\User\PycharmProjects\Mathima 15\askisis 10 merge sort.py", line 32, in <module>
merge_sort(my_list)
File "C:\Users\User\PycharmProjects\Mathima 15\askisis 10 merge sort.py", line 21, in merge_sort
elif len(sorted_right) == 0:
^^^^^^^^^^^^^^^^^
TypeError: object of type 'NoneType' has no len()
Process finished with exit code 1
If you're going to use the return value from a recursive function in the function, it needs to return in every scenario. Your else branch has no such return. The solution is simple: return sorted_part.
def merge_sort(array):
if len(array) == 1:
return array
elif len(array) == 2:
if array[0] > array[1]:
array[0], array[1] = array[1], array[0]
return array
else:
sorted_part = []
left = array[:len(array)//2]
right = array[len(array)//2:]
sorted_left = merge_sort(left)
sorted_right = merge_sort(right)
for i in range(len(array)):
if len(sorted_left) == 0:
sorted_part.extend(sorted_right)
break
elif len(sorted_right) == 0:
sorted_part.extend(sorted_left)
break
else:
if sorted_left[0] < sorted_right[0]:
sorted_part.append(sorted_left.pop(0))
else:
sorted_part.append(sorted_right.pop(0))
return sorted_part
The print at the end of the function is extraneous now as it would never be reached.
This also seems like a good place to apply the match/case syntax introduced in Python 3.10.
def merge_sort(array):
match array:
case [_]: return array
case [a, b] if a < b: return array
case [a, b]: return [b, a]
case _:
sorted_part = []
left = array[:len(array)//2]
right = array[len(array)//2:]
sorted_left = merge_sort(left)
sorted_right = merge_sort(right)
for i in range(len(array)):
if len(sorted_left) == 0:
sorted_part.extend(sorted_right)
break
elif len(sorted_right) == 0:
sorted_part.extend(sorted_left)
break
elif sorted_left[0] < sorted_right[0]:
sorted_part.append(sorted_left.pop(0))
else:
sorted_part.append(sorted_right.pop(0))
return sorted_part
As a sidenote: array is a potentially misleading name for a list.
You may also wish to return a new list in the simpler cases.
case [_]: return list(array)
case [a, b] if a < b: return list(array)