Clarificaiton des Base Case benötigt mit mergeSort

Question

Ich weiß, das ist eine sehr einfache Frage, aber ich lerne selbst, also bitte bitte mit mir!

Im Wikipedia-Pseudocode mergeSort (siehe unten) ist der Terminal-Fall, wenn die Länge des Arrays/Liste kleiner oder gleich eins ist. In den Kommentaren sagen sie, wenn es die Länge von 0 oder 1 ist, dann ist es sortiert. Dem stimme ich zu, aber ich bin neugierig, bedeutet dies, dass mergeSort nicht funktioniert, wenn der Code if (length == 1) hatte? Ich bin nur verwirrt, wie ein Array möglicherweise in eine 0 Länge Array aufgeteilt werden könnte. Würde es nicht schon aufhören, wenn die Länge gleich 1 wäre?

Answer 1

Der Algorithmus ist rekursiv, was bedeutet, dass die Funktion die Liste aufteilt und sich dann mit jedem Teil aufruft. Um die Rekursion zu beenden, wäre if (length == 1) ausreichend, da es niemals eine leere Liste als Ergebnis der Aufteilung geben würde. Du hast das richtig verstanden.

Aber der Benutzer kann diese Funktion mit einer leeren Liste aufrufen. Das muss also auch gefangen werden. Daher die if (length <= 1) (if length of m ≤ 1 then return m).