What makes this code recurse so many times? I was expecting to have a number of iterations much lower than 999.
I tried hard-coding the list of values (which is what you see in the version I gave) and reducing the number of elements in the list: With a single element, the code runs great, but anything above that raises the error seen below.
def main():
list_to_sort: list[int] = [50, 3, 500, 90, 1, 1]
def sort(param_to_sort: list[int]) -> list[int]:
param_len = len(param_to_sort)
if param_len == 1:
return param_to_sort
else:
half_len: int = param_len // 2
list1: list[int] = sort(param_to_sort[0:half_len])
list2: list[int] = sort(param_to_sort[half_len:-1])
if list1[-1] <= list2[0]:
return [*list1, *list2]
else:
return [*list2, *list1]
sorted_list: list[int] = sort(list_to_sort)
print(f"The sorted list is as follows:\n{sorted_list}")
if __name__ == '__main__':
main()
The error returned is as follows:
Traceback (most recent call last):
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 31, in <module>
main()
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 22, in main
sorted_list: list[int] = sort(list_to_sort)
^^^^^^^^^^^^^^^^^^
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 15, in sort
list2: list[int] = sort(param_to_sort[half_len:-1])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 15, in sort
list2: list[int] = sort(param_to_sort[half_len:-1])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
list1: list[int] = sort(param_to_sort[0:half_len])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
list1: list[int] = sort(param_to_sort[0:half_len])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 14, in sort
list1: list[int] = sort(param_to_sort[0:half_len])
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
[Previous line repeated 992 more times]
File "/home/aengusb/Desktop/PyCharmProjects/recursiveSort/recursiveSort.py", line 13, in sort
half_len: int = (param_len / 2).__floor__()
^^^^^^^^^^^^^^^^^^^^^^^^^^^
RecursionError: maximum recursion depth exceeded while calling a Python object
The line numbers might not match exactly because I have a few commented-out lines from trying to figure this issue out myself.
The problem is that you bump into an infinite recursion.
This is caused by param_to_sort[half_len:-1], which excludes the value at -1, i.e. the last value. This will cause endless recursion when the size of param_to_sort is 2, making this slice empty, and you have no base case treatment for empty lists.
To slice from half_len onwards, do param_to_sort[half_len:]: now you won't skip the last value in the list.
Related to this: you should foresee the case where the list is empty. You can use the base case you already have implemented and also execute it when the list size is 0 instead of 1.
Another issue is that in the merge step you just foresee two possible arrangements: either the whole of list1 to come before the whole of list2, or vice versa. But there are more possibilities. For instance, if list1 is [2, 4] and list2 is [1, 3] you don't want [*list1, *list2] nor [*list2, *list1]. You'll want to "weave" the values from these lists, which often requires that you make more than one comparison and step by step pick a value from either list. There are several ways you can implement that merge step.
Here is how you could make it work:
def sort(param_to_sort: list[int]) -> list[int]:
param_len = len(param_to_sort)
if param_len <= 1: # Also when list is empty
return param_to_sort
else:
half_len: int = param_len // 2
list1: list[int] = sort(param_to_sort[:half_len])
list2: list[int] = sort(param_to_sort[half_len:]) # Fix
# Merge step needs to check how to "weave" the two lists
merged: list[int] = []
while list1 and list2:
source: list[int] = list1 if list1[-1] > list2[-1] else list2
merged.append(source.pop()) # add greatest
return list1 + list2 + merged[::-1]