.:: Informationen zu Mergesort ::.

Mergesort sortiert eine Folge von Elementen durch das Mischen zweier sortierter Folgen.
Hierzu wird die zu sortierende Folge zunächst rekursiv solange halbiert, bis einelementige
Folgen entstehen. Diese werden dann durch Mischen zusammengefügt. Nach Beendigung der
Rekursion wird die zweite Teilfolge sortiert und durch Mischen mit der ersten verschmolzen.

Zu beachten ist dabei, dass zur Beschleunigung des Verfahrens beim Mischen die Daten in ein
zweites Feld kopiert werden, wobei die erste Folge aufsteigend, die zweite hingegen in
absteigender Folge kopiert wird. Hierdurch spart man sich beim Bestimmen des nächsten
einzufügenden Elements jeweils den Test, ob man bereits über eine Teilfolgengrenze gelaufen
ist.

Anzahl der Schritte, die zum Sortieren nötig sind:
- O(n*log(n)); Mergesort benötigt aber zusätzlichen Speicherplatz von O(n).


  • Hier Java Programm runterladen

    • .: Zurück zum Menü