Python merge Sortierproblem

Question

Nicht sicher, wo ich falsch mit meiner Implementierung von merge sort in Python bin.

import sys 

sequence = [6, 5, 4, 3, 2, 1] 

def merge_sort(A, first, last): 
    if first < last: 
     middle = (first + last)/2 
     merge_sort(A, first, middle) 
     merge_sort(A, middle+1, last) 
     merge(A, first, middle, last) 

def merge(A, first, middle, last): 
    L = A[first:middle] 
    R = A[middle:last] 

    L.append(sys.maxint) 
    R.append(sys.maxint) 

    i = 0 
    j = 0 
    for k in xrange(first, last): 
     if L[i] <= R[j]: 
      A[k] = L[i] 
      i = i + 1 
     else: 
      A[k] = R[j] 
      j = j + 1 

merge_sort(sequence, 0, len(sequence)) 
print sequence 

Ich würde es wirklich schätzen, wenn jemand darauf hinweisen könnte, was meine aktuelle Implementierung von merge sort bricht.

Answer 1

Das Problem sein:

merge_sort(A, first, middle) 
    merge_sort(A, middle+1, last) # BEEP 

Sie nur sortieren die s Zweiter Teil von Mitte + 1, wenn Sie in der Mitte beginnen sollten. Tatsächlich ordnen Sie das Element nie in der Mitte neu an.

Natürlich können Sie auch nicht

merge_sort(A, first, middle) 
    merge_sort(A, middle, last) # BEEP, BEEP 

schreiben, denn wenn last = erste + 1, Sie Mitte bekommen == erste und tauchen in einer endlosen Rekursion (gestoppt durch eine RuntimeError: maximum recursion depth exceeded)

So ist die Art und Weise zu gehen ist:

merge_sort(A, first, middle) 
    if middle > first: merge_sort(A, middle, last) 

Nach dieser kleinen Änderung gibt Ihre Implementierung korrekte Ergebnisse.

Answer 2

Es gibt zwei Fehler im Code:

• if first < last: sollte if first < last and last-first >= 2:
• merge_sort(A, middle+1, last) sollte, ist hier merge_sort(A, middle, last)