なぜこのようにマージソートを実装できないのですか？

Question

mergesortは分裂と征服によって理解できます。一定の時間内にソートできるか、またはリストが1つだけのもので、リストをマージするまで、 。

def mergesort(l): 
    if len(l)<=1: 
     return l 
    l1 = l[0:len(l)//2+1] 
    l2 = l[len(l)//2:] 

    l1 = mergesort(l1) 
    l2 = mergesort(l2) 

    return merge(l1,l2) 

は私が作業マージの実装を持っていると私はそれが正常に動作しますが、マージソートの実装はそれだけでリストの要素の半分を返す動作しません確認しました。

インターネットで見ると、mergesortはl & rとm =（l + r）/ 2を使用して実装されています。実装で何が問題になっていますか？私は再帰的にリストを細分化し、併合しています。

Answer 1

あなたがリストしたコードはソートを行っていないようです。あなたがmerge（）関数のコードを列挙していないので、私は確かにわかりませんが、上記の関数が行う唯一のことはリストを再帰的に半分に分割することです。

def mergeSort(L): 

    # lists with only one value already sorted 
    if len(L) > 1: 
     # determine halves of list 
     mid = len(L) // 2 
     left = L[:mid] 
     right = L[mid:] 

     # recursive function calls 
     mergeSort(left) 
     mergeSort(right) 

     # keeps track of current index in left half 
     i = 0 
     # keeps track of current index in right half 
     j = 0 
     # keeps track of current index in new merged list 
     k = 0 

     while i < len(left) and j < len(right): 
      # lower values appended to merged list first 
      if left[i] < right[j]: 
       L[k] = left[i] 
       i += 1 
      else: 
       L[k] = right[j] 
       j += 1 
      k += 1 

     # catch remaining values in left and right 
     while i < len(left): 
      L[k] = left[i] 
      i += 1 
      k += 1 

     while j < len(right): 
      L[k] = right[j] 
      j += 1 
      k += 1 
    return L 

この機能では、元のリストの値を比較しません。あなたが半分にリストを分割している場合にも、：

l1 = l[0:len(l)//2 + 1] 

「+ 1」不要である（そして、実際に間違った解決策を引き起こす可能性があります）。長さがあっても（すなわち、12）である場合、それはから二つの半体を分割する

l1 = l[:len(l)//2] 

：あなたは、単に使用することができ[0：6]および[6：12]。それが奇数の場合、それはまだ自動的に正しく分割されます（つまり、長さは= 13のようになります。[0：6]と[午前6時13分]私は願ってこのことができます

Answer 2

問題はここに、あなたのコードで+1次のとおりです！

l1 = l[0:len(l)//2] 
l2 = l[len(l)//2:] 

それは半分だけを返し、なぜあなたのコードでこれを交換し、あなたが