なぜPythonのマージソートが最大再帰深度を超えましたか？

Question

私はMITのオープンコース6.046「Introduction to Algorithms」をYoutubeで学んでおり、私はPythonでマージソートを実装しようとしていました。

私のコードは

def merge(seq_list, start, middle, end): 
    left_list = seq_list[start:middle] 
    left_list.append(float("inf")) 
    right_list = seq_list[middle:end] 
    right_list.append(float("inf")) 
    i = 0 
    j = 0 
    for k in range(start, end): 
     if left_list[i] < right_list[j]: 
      seq_list[k] = left_list[i] 
      i = i + 1 
     else: 
      seq_list[k] = right_list[j] 
      j = j + 1 


def merge_sort(seq_list, start, end): 
    if start < end: 
     mid = len(seq_list)/2 
     merge_sort(seq_list[0:mid], start, mid) 
     merge_sort(seq_list[mid:], mid, end) 
     merge(seq_list, start, mid, end) 

され、単体テストのコードは

import unittest 
from sorting import * 

class SortingTest(unittest.TestCase): 
    def testMergeSort(self): 
     test_list = [3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5] 
     merge_sort(test_list, 0, 9) 
     self.assertEqual(test_list, [0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]) 
    def testMerge(self): 
     test_list = [13,17,18,9,2,4,5,7,1,2,3,6,0,38,12] 
     merge(test_list, 4, 8, 12) 
     self.assertEqual(test_list, [13,17,18,9,1,2,2,3,4,5,6,7,0,38,12]) 


if __name__ == "__main__": 
    unittest.main() 

機能マージ（で）完璧に動作ようだが、merge_sort（）関数が間違っていた、と私は知りませんどうしたの。ターミナルは私を示しています

RuntimeError: maximum recursion depth exceeded

Answer 1

あなたは[と実際に同じリストにとどまる]他の賢明なあなたは、空のリストを「縮小」を維持、リストが空またはサイズ1である場合、ベース句を追加する必要があります。

EDIT：時々あなたがlen(seq)いくつかの回を使用している、そしてstart、end - あなたはちょうどそれらのいずれかに固執する必要があります

はまた、私はそれが実際には別のバグから導出されると思います。今、あなたは

mergesort([2,3],2,3) #2 == mid, 3 == end 

で再帰以降必要になります>半ば= 2

-

mid = len(seq_list)/2 
    merge_sort(seq_list[0:mid], start, mid) 
    merge_sort(seq_list[mid:], mid, end) 

は、テストケース[0,1,2,3]

スタート= 0、終了= 3の表情を持っていますセット：

mid = len([2,3])/2 == 1 

mergesort([3],1,3) 

で再び再帰的としてみてくださいあなたはendが変わることはありませんので、start >= endの「停止条件」に到達しないと、現在のリストの範囲外にあるんでしょう！

別のバグ：

merge_sort(seq_list[0:mid], start, mid) 

がseq_listに何もしない、それはそれを変更しない - それはあなたが再帰にpassd新しいリストオブジェクトを変更し、ひいてはmerge()も失敗します。