Pythonはアイブ氏は、スライシングを使用せずにクイックソートの実装を作成しようとし

Question

をスライスせずにマージソートが、私は、実行時の途中での問題に実行しているよ - 私は間違って私は「

を行くよどこ誰もが私を見ることができればと思いまして（コメントアウト）いくつかのprint文を追加しましので、あなたは前に起こっていただきました！見ることができ、各ステージの後：

def mergesort(arr, l, r): 

    #print('start: ', arr[l:r]) 

    if len(arr[l:r]) <=1: 
     return arr[l:r] 

    mid = l + (r-l) // 2 
    left = mergesort(arr, l, mid) 
    right = mergesort(arr, mid, r) 

    l_idx = l 
    r_idx = mid 
    final = [] 

    while l_idx < mid and r_idx < r: 
     if arr[l_idx] <= arr[r_idx]: 
      final.append(arr[l_idx]) 
      l_idx+=1 
     else: 
      final.append(arr[r_idx]) 
      r_idx+=1 


    for val in arr[l_idx:mid]: 
     final.append(val) 

    for val in arr[r_idx:r]: 
     final.append(val) 

    #print('final: ', final[l:r]) 
    #print() 
    #print() 
    return final 



    print(merge([0, 9, 3, 7, 4, 2, 6, 1], 0, 8)) 

私は左サイドを持っていたため、それがうまく機能していることショーを取得していた値が、右のそれのためにしません。左の右側のために働くように見えるので、好奇心旺盛です...

stdoutがある：

start: [0, 9, 3, 7, 4, 2, 6, 1] 
start: [0, 9, 3, 7] 
start: [0, 9] 
start: [0] 
start: [9] 
final: [0, 9] 


start: [3, 7] 
start: [3] 
start: [7] 
final: [] 


final: [0, 3, 7, 9] 


start: [4, 2, 6, 1] 
start: [4, 2] 
start: [4] 
start: [2] 
final: [] 


start: [6, 1] 
start: [6] 
start: [1] 
final: [] 


final: [] 


final: [0, 4, 2, 6, 1, 9, 3, 7] 

Answer 1

主な問題は、あなたが返されますleftとrightリストを使用しないということです再帰的な呼び出しから、arrはこれらの呼び出しによって1ビットも変更されていないため、これらは必要です。また、これを修正するときは、再帰呼び出しによって渡されたlの値に関係なく、この結果のリストがインデックス0から開始されることにも注意してください。つまり、実際のマージループはlではなく、インデックス0から開始する必要があります。この変更it will workで

# concatenate the left and right results into arr 
arr = left + right 

# realign the indexes with the new arr 
mid -= l 
r -= l 
l_idx = 0 
r_idx = mid 

：ここ

あなたは再帰呼び出した後、右が必要ですコードです。

NB：これをスライスせずに行いたいと言ったが、:の表記を使用するたびにスライスすることに注意してください。arr[l:r]のようにスライスします。