Ist es möglich die mergeSort() Methoden ohne eine verkettete Liste zu lösen?
Jeglicher Versuch scheitert nämlich bisher, deshalb rückt mir der Verdacht immer näher dass ich eine verkettete Liste benutzen muss…
Geht auch ohne Listen 
sondern mit was?
Auf die Gefahr hin deine Frage komplett falsch zu verstehen, aber du bekommst in der Aufgabe doch Array übergeben und die linke und rechte Grenze des Unterarrays. Was spricht dagegen mit denen zu arbeiten? Das Teilen ist mittels der beiden Grenzen nicht weiter schwer, der Mergeteil im wesentlichen (sofern man es schon einmal gesehen hat ;-)) auch nicht… ? An welche Schritt liegts denn?
Ich verstehe nicht ganz was ich bei dieser Methode machen soll:
public static void mergeSort(Object[] data, int fromIndex, int toIndex, Object[] temp) {
Nochmal das gleiche wie schon hier: public static void mergeSort(Object[] data, int fromIndex, int toIndex) {
nur das ich, anstatt selbst ein temporäres Array zu erstellen, in das im Parameter gegebene zwischenspeicher?
Was soll das überhaupt bringen? Ob ich jetzt in der aufrufenden oder in der ausführenden Methode ein tmp-Array erstelle, ist doch egal?
Das Mischen kann nicht im original Array stattfinden und wird daher in einem temporären Array erledigt. Jetzt ist Merge-Sort rekursiv. Hättest du also nur eine Merge-Sort Methode und würdest den temporären Array in selbiger alloziieren, würdest du zig Mal einen Array erzeugen. Stattdessen kannst du auf jeder Ebene des Merge-Sort denselben Array verwenden. Damit du den aber nur einmal anlegst, benötigst du eine umschließende mergeSort-Methode, in der die Initialisierung stattfindet.
Hm, was soll denn in dieser Methode überhaupt gemacht werden?
Der Kommentar “* Fuehrt die eigentliche Sortierung durch” hilft mir nicht weiter.
Ist damit nun der rekursive oder iterative Teil gemeint?
Das könnte man so und so interpretieren, die “eigentliche Sortierung” wird doch eigentlich durch die Kombination von beidem erreicht.
Die Methode ist ja als private Hilfsmethode gedacht, von wo wird diese denn überhaupt betätigt?
Von den beiden anderen MergeSort-Methoden?
Heißt das, ich brauche nur diese eine Merge-Sort Implementierung mit dem tmp-Array als Parameter oder auch eine “klassiche” ohne?
Merge auf Arrays ist ein bisschen schwieriger als mit Listen, deshalb kann man ein temporäres Array einführen das beim mergen nach und nach mit den richtigen Ergebnissen gefüllt wird. Am Ende muss es wieder ins original kopiert werden …
Die anderen beiden merge–sort Methoden sollen eigentlich nichts anderes machen, als diese Hilfsmethode mit den richtigen Parametern aufzurufen.
Warum man dieses temp-Array ber Methode übergeben wurde ist eine gute Frage. Vielleicht damit es bei jedem rekursiven Aufruf nicht neu initialisiert werden muss (Stichwort Performance), aber das ist nur eine Vermutung.
Ok, also die ersten beiden MergeSort-Methoden machen nichts weiter als die dritte aufzurufen,
welche dann den eigentlichen MergeSort-Algorithmus betätigt (entweder in sich selbst oder mit weiteren Hilfsmethoden).
Soweit so gut, allerdings brauche ich für den Merge-Schritt doch zwei sortierte Teil-Array’s und ein Ergebnis-Array,
also komme ich doch trotzdem nicht drum-hermum etwas mehrmals zu initialisieren?
Schau dir die Methodensignatur an. Die bekommt eine linke Grenze (inklusiv) und eine rechte (exklusiv) übergeben. Das ‚teilen‘ beschränkt sich also auf einen rekursiven Aufruf mit den neuen Grenzen (so, dass das alte Array ungefähr in der Mitte geteilt wird).
Es muss eigentlich nur einmal dieses temp-Array angelegt werden, danach nichts mehr …
Ich habe eine Frage betreffends des in der main() ausgeführten Tests.
Dieser gibt mir beim mergeSort immer seine Meldung der “fehlerhaften Implementierung” aus, obwohl ich mir zu 99% Prozent sicher bin, dass ich das ganze sauber implementiert habe, und dies auch durch eigene kleine Tests getestet habe.
Also hab ich mir den durchgeführten Vergleich näher angeschaut:
if(ms[i] != js[i]) { ... } Ich habe gelesen, dass Java bei den Wrapper Klassen, hier einen Vergleich der Referenzen durchführt und nicht .equals() oder .compareTo() aufruft(ersetze ich die Abbruchbedingung mit einer von diesen beiden Methoden, kommt es bei mir zu keinem Fehler).
Da die Arrays zufällig initialisiert werden, kommt es vor, dass doppelte Integer erzeugt werden; und da diese zwar beim .compareTo() als gleich angesehen werden (weswegen die Sortierung trotzdem stimmt), allerdings von meinem mergeSort() und von Javas sort() in unterschiedlicher Reihenfolge einsortiert werden, bricht der vorgegebene Text ab (da an Stelle i ms[i] und js[i] zwar den gleichen Wert haben, aber leider nicht die selben Referenzen).
Die Frage: Ist meine Implementierung trotzdem ok, weil sie augenscheinlich die Werte richtig sortiert, oder muss ich die Objekte in exakt die selbe Reihenfolge bringen wie Java-Sort?
Gruß!
Nicht schlecht. Du hast dir in eigener Arbeit eine Erkenntnis erarbeitet, die man dir auch in der Vorlesung/Übung vermittelt hätte 
Man spricht hier von stabiler/instabiler Sortierung. Die Übung (hier ein Zitat aus dem Skeleton), verlangt aber explizit eine stabile Sortierung:
/**
* ...
* Das Verfahren sortiert stabil.
* ...
*/Deine Implementierung ist also solange nicht vollständig korrekt, solange der Referenzvergleich nicht durchläuft.
EDIT: Zu früh auf Post geklickt 
Auch hier wieder die übliche Frage.
Ist es ok in dieser Aufgabe eine unchecked Operation Warning zu kriegen? (Speziell bei insertionsort())
Warning != Fehler => ok 
Tja Übung hatte ich noch nicht, und Vorlesung … habe ich zu dem Thema nicht besucht
Jetzt weiß ich auch endlich, was diese stabile Sortierung sein soll, und siehe da, durch Einsetzen eines einzigen Zeichens in meinen Code läuft der Referenzvergleich jetzt durch. Sehr gut.
dürfen wir davon ausgehen, dass die übergebenen array keine “null”-stellen enthalten.
also das data[x] != null, oder müssen wir das abfangen. denn compareTo() liefert ja eine NullPointerException, wenn einer der werte null ist.
Normalerweise ist die Abbruchbedingung von MergeSort doch einfach wenn start >= end ist, richtig? Heißt dass, das wir in unserem Fall diese Abbruchbedingung einfach nur durch eine Überprüfung von Switch ersetzen? Also wenn das Array die Länge von Switch erreicht, die Rekursion abbricht?! Oder wird diese Bedingung erst weitere unten im Code, also erst beim Zusammenmischen der Arrays verwendet? Bekomme irgendwie ständig einen Stackoverflow, wenn ich Switch als Abbruch verwende und dann Insertion aufrufe… Aber evtl liegts auch an was anderem
Andernfalls wäre es sehr schwierig ja. Arrays.sort(abc) funktioniert auch nicht mit null-Werten 
Stackoverflow hört sich eher nach einer Endlosrekursion an. Bist du dir sicher, dass früher oder später ein Basisfall erreicht wird?
Noch eine Frage:
Man kann das alles mit dieser einen Methode machen? Also mergen und sorten?
Habe immer nur Implementierungen gesehen, die einfach dann merge aufrufen.
Und das mit dem tmp array verstehe ich auch noch nicht so ganz.
Implementier mal den Merge Teil inplace (also nur mit dem gegebenen Array) und dir fällt ganz schnell auf wozu man ein zweites brauchen kann