I can’t figure out what about this code makes it recurse so many times. I would appreciate any tips to make it not do that.

I was expecting to have a number of iterations much lower than 999.

I tried to look up this issue on StackOverflow and elsewhere, but none really helped me fix my code. 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. Sorry about that.