Also wenn du nach Namen sortierst, sollten die Datensätze natürlich nur nach Namen sortiert sein (unabhängig von den Geburtsdaten usw.). Stabil ist ein Sortierverfahren eigentlich nur dann, wenn die Eingabereihenfolge bei gleichen Datensätzen erhalten bleibt. Hast du also ein Feld, hier einfach mal Tupel aus einer Zahl und einem Namen und sortierst nach dem Namen, so ist ein
[(Maier, 1), (Rudi, 2), (Maier, 2)] -> [(Maier, 1), (Maier, 2), (Rudi, 2)] stabil
[(Maier, 1), (Rudi, 2), (Maier, 2)] -> [(Maier, 2), (Maier, 1), (Rudi, 2)] nicht stabil
wobei natürlich die Reihenfolge garantiert werden muss. Also hier, dass wenn der (Maier, 1) vor dem (Maier, 2) in der Eingabe steht, er es auch in der Sortierung tut.
Ich würde dir ehrlich gesagt immer noch dazu raten, deine Implementierung nochmals vor zu nehmen. Nimm wirklich besser Zeiger auf deinen Record. Dann kannst du das mit den Indizes komplett streichen.
Der Mergesort ist sehr abstrakt nur ein
Code:
MergeSort(Feld A) : Feld
begin
wenn Länge(A) = 1 dann
Ergebnis := A;
sonst
Ergebnis := Mische (MergeSort (erste Hälfte von A)) (MergeSort (zweite Hälfte von A))
end;
Mische (Feld A, Feld B) : Feld
begin
// ist klar
end;
Wichtig ist hier, dass dein zurück gegebenes Feld von MergeSort immer ein neu angelegtes Feld ist. Du hast eine Eingabe A, zerteilst die in zwei Felder B und C (in der Mitte), sortierst diese Felder rekursiv und gibst das sortiert-gemischte Feld D zurück. Als Feld kannst du also einfach ein Feld von Zeigern auf deine Datensätze verwenden. Dann sortierst du die Pointer (nur 4 Byte), hast aber zum Sortieren die Daten hinter den Pointern zur Verfügung (nur bewegst du diese Daten nie im Speicher).
Hoffe ist etwas klarer. Sorry, hab deine Idee mit dem Indexverschieben zwar (denke ich) verstanden, denke aber dass es überflüssig und fehleranfällig ist (weswegen ich dort nicht nach Fehlern schauen möchte). Zudem greifst du irgendwie (soweit es ein kurzer Blick mir zeigt) auf dein eigentliches Eingabefeld zu. Und dass darf halt nicht sein. Du darfst nicht im eigentlichen Eingabefeld mischen.
Du merkst dir deine Teilfelder ja etwas virtuell (Start und Endindex). Ich versuch es mal zu visualisieren.
Eingabe : [1,2,3,1,2]
StartIndex : S, Endindex E
Teilfelder (nach ein paar Aufrufen) :
[1,2,3] [1,2] <- -> [1,2,3,1,2]
S E S E // hier jetzt dein Rechts, Links dass du dir merkst.
Jetzt mischt und sortierst du also:
Eingabefeld:
[1, 2, 3, 1, 2]
S E S E // das erste Element ist sortiert, du betrachtest nun die zwei ersten unsortierten
[1, 1, 3, 2]
S E SE // ups, jetzt hast du dein Problem, du überschreibst dir einen Wert (Stelle 2 in der Eingabe) wenn du nur mit einem Index arbeitest.
Hoffe du siehst grob was ich meine. Deshalb kannst du halt nicht in-place sortieren. Also musst du ein eigenes Array zur Rückgabe verwenden und kannst nicht nur über die Indizes gehen (dass klappt z.B. mit Quicksort oder Bubblesort, die in-place sortieren).