Pythonでmergesortの中間点を見つける

Question

私はmergesortアルゴリズムの2つの異なる実装を書いていますが、それを分割する配列の中点を見つけるのに使われる式の違いは1つだけです。

最初の実装：（正しく実行）

def mergesort(arr): 
    start = 0 
    end = len(arr) - 1 
    if len(arr) > 1: 
     mid = int(len(arr)/2) 
     left = mergesort(arr[:mid]) 
     right = mergesort(arr[mid:]) 
     return merge(left,right) 
    else: 
     return arr 

def merge(left,right): 
    final = [] 
    while len(left) > 0 or len(right) > 0: 
     if len(left) > 0 and len(right) > 0: 
      if left[0] < right[0]: 
       final.append(left[0]) 
       del left[0] 
      elif right[0] < left[0]: 
       final.append(right[0]) 
       del right[0] 
     elif len(right) > 0: 
      final.extend(right) 
      right = [] 
     elif len(left) > 0: 
      final.extend(left) 
      left = [] 
    return final 


arr = list(map(int,input().split(' '))) 
print ("List before sorting:",arr) 
final = mergesort(arr) 
print ("After sorting:",final) 

第2の実施形態（無限ループに入った）：

def mergesort(arr): 
    start = 0 
    end = len(arr) - 1 
    if len(arr) > 1: 
     mid = int(start + (end - start)/2) 
     left = mergesort(arr[:mid]) 
     right = mergesort(arr[mid:]) 
     return merge(left,right) 
    else: 
     return arr 

def merge(left,right): 
    final = [] 
    while len(left) > 0 or len(right) > 0: 
     if len(left) > 0 and len(right) > 0: 
      if left[0] < right[0]: 
       final.append(left[0]) 
       del left[0] 
      elif right[0] < left[0]: 
       final.append(right[0]) 
       del right[0] 
     elif len(right) > 0: 
      final.extend(right) 
      right = [] 
     elif len(left) > 0: 
      final.extend(left) 
      left = [] 
    return final 


arr = list(map(int,input().split(' '))) 
print ("List before sorting:",arr) 
final = mergesort(arr) 
print ("After sorting:",final) 

IはクイックソートALGOの場合に用いられる第2の式を見てきました。問題は、私の目的がアレイを分割すること（クイックソートの場合のように）が無限ループに入る理由です。

私は非常に困惑しており、論理的な結論に至ることはできません。

誰かに問題を投げかけてもらえますか？ありがとうございます。

Answer 1

サブ配列の複数のインスタンスではなく、単一の配列で作業する場合は、2番目の方法を使用する必要があります。実際の別個のサブアレイを使用する代わりに、元のアレイはインデックス範囲を介して論理サブアレイに分割されます。 mergesort関数は、3つのパラメータmergesort（arr、start、end）を呼び出し、呼び出し元はmergesort（arr、0、len（arr））を呼び出します。マージ関数は、merge（arr、start、mid、end）の4つのパラメータをとります。

効率は、1つのパラメータmergesort（arr）を取るエントリ関数を使用して改善することができます。 1つの作業配列tmpを割り当てて内部関数に渡すと、mergesort（arr）の呼び出しはmergesort（arr、tmp、0、len（arr））になります。 mergesort関数は、mergesort（arr、tmp、start、end）です。マージ関数は、merge（arr、tmp、start、mid、end）になります。