Hi

ich haette da mal ne Frage zu Merge Sort, die dieser Algoritmus in der Theorie funktioniert glaube ich zu wissen… mit dem Aufteilen bis nur ein Elemant der Liste noch über ist und dann wieder zusammen basteln und so…
Grafiken zu dem Thema gibt es ja reichlich…

Aber wie programmiere ich das jetzt in java?
Mein Problem ist, rekursive glaub ich das aufteilen hinzubekommen…. halt immer weiter aufteilen bis nur noch ein Wert im array ist
aber wie mach ich das mergen?
der Ersten Schritt mergen ist mir (glaub ich) klar…. die beiden Werte die ich hab, mit einander vergleichen, den kleinern als erstes ins neue array stopfen und dann den größeren an 2. stelle….aber dann?
2 Array mit einander vergleichen, aber wie bekomm ich die 2 Arrays aufgerufen?

http://vsis-www.informatik.uni-hamburg.de/teaching/ws-02.03/p3/

Blatt 2, Aufgabe 3

Wobei MergeSort fuer Listen verwendet werden sollte, nicht fuer Reihnungen (Arrays). D.h. bei Ersterem ist er gut (Rechenzeit in O(n log n)), bei Letzterem nicht so, da die Speicherkomplexitaet bei Reihungen in O(n) liegt.

Das du Probleme mit dem Mergen hast ist eigentlich kein Wunder, da dies ein "easy split/hard join"-Verfahren ist, liegt dort die ganze Arbeit :) (bei Quicksort war dies ja genau andersherum).

Vgl. hierzu bspw. "Einführung in die Informatik" von Küchlin/Weber oder die Buecher von Güting/Dieker oder Saake/Sattler.

Cheers.