Mergesort
Mergesort ist ein interaktives Experiment in Algorithmen sichtbar gemacht, einer kostenlosen Simulation aus dem StudyFi Lab, die direkt im Browser läuft.
Mergesort teilt das Array in zwei Hälften, sortiert jede auf dieselbe Weise (Rekursion) und verschmilzt dann die beiden sortierten Hälften: Es nimmt immer das kleinere der beiden vorderen Elemente. Das Halbieren ergibt log₂ n Ebenen, und jede Ebene verarbeitet alle n Elemente, die Laufzeit ist also immer O(n log n). Bei Gleichstand nimmt es das linke Element, deshalb ist es stabil.
Probier das: Probiere ein umgekehrtes und dann ein fast sortiertes Array gleicher Größe. Die Zahl der Vergleiche ändert sich kaum — die Reihenfolge der Eingabe spielt fast keine Rolle.
Häufige Fragen
Was zeigt das Experiment „Mergesort“?
Mergesort teilt das Array in zwei Hälften, sortiert jede auf dieselbe Weise (Rekursion) und verschmilzt dann die beiden sortierten Hälften: Es nimmt immer das kleinere der beiden vorderen Elemente. Das Halbieren ergibt log₂ n Ebenen, und jede Ebene verarbeitet alle n Elemente, die Laufzeit ist also immer O(n log n). Bei Gleichstand nimmt es das linke Element, deshalb ist es stabil.
Wie probiere ich „Mergesort“ aus?
Probiere ein umgekehrtes und dann ein fast sortiertes Array gleicher Größe. Die Zahl der Vergleiche ändert sich kaum — die Reihenfolge der Eingabe spielt fast keine Rolle.
Lernst du für eine Prüfung?
Lade deine Notizen hoch und StudyFi macht daraus Karteikarten, Tests und Podcasts.