Как решить проблему рекурсии в алгоритме сортировки слиянием?

Question

В примере я хочу отсортировать атрибут f станции, используя сортировку слиянием.

class mergesort_algorithm():


 def Merge_Sort(self,stations):

     length = len(stations)
     middle = int(length/2-1)

     if length<=1:
         return stations
     else:
         list1 = self.Merge_Sort(stations[:middle])
         list2 = self.Merge_Sort(stations[middle:])

         return self.Merge(list1,list2)




 def Merge(self,list1,list2):
     list3 = []
     length1 = len(list1)
     length2 = len(list2)
     point1 = 0
     point2 = 0


     while point1<=length1-1 and point2<=length2-1:

         if list1[point1].f<list2[point2].f:
             list3.append(list1[point1])
             point1 += 1

         else:
             list3.append(list2[point2])
             point2 += 1

     if point1>length1:
         for i in range(list2):
             if i>=point2:
                 list3.append(list2[point2])

     if point2>length2:
         for i in range(list1):
             if i>=point1:
                 list3.append(list1[point1])

     for item in list3:
         print(item.name)
     print("-----")
     return list3

Когда я запускаю коды для сортировки списка станций, он сообщает об ошибке.

File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 16, in Merge_Sort
    list1 = self.Merge_Sort(stations[:middle])
  File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 17, in Merge_Sort
    list2 = self.Merge_Sort(stations[middle:])
  File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 17, in Merge_Sort
    list2 = self.Merge_Sort(stations[middle:])
  File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 17, in Merge_Sort
    list2 = self.Merge_Sort(stations[middle:])
  [Previous line repeated 989 more times]
  File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 16, in Merge_Sort
    list1 = self.Merge_Sort(stations[:middle])
  File "/home/surface/Final-Year-Project/FYP/Util/Mergesort_algorithm.py", line 11, in Merge_Sort
    middle = int(length/2-1)
RecursionError: maximum recursion depth exceeded while calling a Python object

Я не знаю, как это решить. Кажется, что так много рекурсий. И я нашел какое-то решение использовать: import sys и sys.setrecursionlimit (1000000)

Answer 1

Предположим, len(stations) равно 2. Тогда middle равно 0. Таким образом, stations[:middle] пусто, но stations[middle:] имеет длину 2 и существует бесконечная рекурсия.