Meine Merge-Sortierung in Python-Code gibt 0 zurück [0]

Question

Ich mache Merge-Sortiercode, aber es sortiert nicht. Siehst du, was damit nicht stimmt?

def mergeSort(L): 
if len(L) == 1: 
    return L 
else: 
    # divide 
    L1 = mergeSort(L[0:round(len(L)/2)]) 
    L2 = mergeSort(L[round(len(L)/2):len(L)]) 

    # merge 
    i = 0 
    j = 0 
    K = [] 
    while i < len(L1) and j < len(L2): 
     if L1[i] < L2[j]: 
      K.append(L1[i]) 
      i=i+1 
     else: 
      K.append(L2[j]) 
      j=j+1 
    return K 

Eingang:

L = [1,2,5,7,8,0,10,21,32,53,16,16,48,59,64,53,75,52,42,21,98,76‌​] 

Ausgang:

L = [0] 

Answer 1

while i < len(L1) and j < len(L2): 

Dies sieht nicht richtig für mich. Mit dieser Bedingung endet die Schleife, sobald entweder i oder j das Ende ihrer jeweiligen Liste erreicht. Es kann immer noch Elemente in der anderen Liste geben, die dadurch nie iteriert werden.

Versuchen, dass and auf ein or ändern, und einige sicher, dass Inter-Liste Vergleich geschieht nur, um die Überprüfung hinzufügen, wenn weder die Liste vollständig noch wiederholt wurde:

while i < len(L1) or j < len(L2): 
     if i < len(L1) and (j == len(L2) or L1[i] < L2[j]): 
      K.append(L1[i]) 
      i=i+1 
     else: 
      K.append(L2[j]) 
      j=j+1 

Jetzt [0, 1, 2, 5, 7, 8, 10, 16, 16, 21, 21, 32, 42, 48, 52, 53, 53, 59, 64, 75, 76, 98] Code-Ausgänge.

Answer 2

Betrachten Sie die folgende Zeile:

while i < len(L1) and j < len(L2): 

Zum Beispiel, wenn alle Elemente in L1 sind kleiner als alle Elemente in L2 dann dieser Schleife wird K alle Elemente in L1 in das Ergebnis setzen. Die Schleife wird dann beendet und L2 wird ignoriert. Sie müssen die restlichen Elemente aufräumen, wenn diese Schleife beendet ist. Fügen Sie diese Codezeile unmittelbar nach der Schleife:

K.extend(L1[i:] + L2[j:]) 

By the way, fand ich dies mit einem Debugger durch den Code treten, mit Eingang L=[2,1]. Ich fand, dass, wenn ich nur die while Schleife für eine Iteration durchging, und da ein Element jeder Schleife Iteration hinzugefügt wird, konnte dort nur ein Element im Ergebnis sein. Wenn Sie nicht bereits wissen, wie Sie mit einem Debugger durch den Code gehen, sollten Sie jetzt lernen.