比較エラーpythonで最大再帰深度を超えましたか？

Question

mergesortを使って数字のリストをソートし、ソート方法（バブル、選択など）によってさまざまな長さのリストをソートするのにかかる時間がどのように異なるか比較します。シャッフルシャッフルソートのための私のコードで、これはマージソートと選択ソートに変更します

k=0 
times=[] 

while k<n: 
    x=list(range(1,2**k)) 
    shuffle(x) 
    start=clock() 
    selectionsort(x) 
    end=clock() 
    times.append(end-start) 
    k=k+1 
return(times) 

：だから私はこれをテストするために、次のコードを使用します。シャッフルソートと選択ソートをテストすると、必要に応じてコードが実行されますが、mergesortをテストすると、比較エラーで最大再帰深度を超えます。次のようにマージソートのための私のコードは次のとおりです。

def mergesort(list): 
    if len(list) == 1: 
     return list 

    m = len(list)//2 
    l = mergesort(list[:m]) 
    r = mergesort(list[m:]) 

    if len(l)<1 or len(r)<1: 
     return l or r 

    result = [] 
    i = j = 0 
    while (len(result)<len(r)+len(l)): 
     if l[i] < r[j]: 
      result.append(l[i]) 
      i = i+1 
     else: 
      result.append(r[j]) 
      j = j+1 
     if i == len(l) or j == len(r): 
      result.extend(l[i:] or r[j:]) 
      break 
    return result 

私はこのエラーを取得される可能性がありますなぜ、誰でも提案することができますか？前もって感謝します！

Answer 1

引数が渡された場合、mergesort関数は正しく機能しません。空のリストです。長さがちょうど1であるときにあなたのベースケースがそれを止めるので、それは永遠に繰り返されます。

ドライバコードはlist(range(1,2**k))とkのソートコードが最初は0であるため、最初の繰り返しで空のリストが得られます（range(1, 1)は空です）。この問題を解決するには

、リストが空の場合（ソートするための何もないので）を停止するためにあなたのソートの基本ケースを変更：

def mergesort(list): 
    if len(list) <= 1: # less than or equal! 
     return list 

ワン（あなたの問題に関係のない）さらに提案：それはです変数名としてlistを使用することは非常に悪い考えです。すると、組み込みのlistタイプがマスクされ、混乱するバグが発生する可能性があります。一般的な方法はlstです（ただし、必要に応じてわかりやすい名前を使用できます）。