Hi,
also ehrlich gesagt ist dass eine doch eher ungewöhnliche Implementierung des Mergesort. Ich weiß ja nicht was du genau vergleichen möchtest, aber wenn es um die Asympotischen Laufzeiten geht (die bei Mergesort theoretisch besser ist), dann solltest du nicht mit gerade einmal 1000 Datensätzen arbeiten. In dieser Laufzeit sind verschiedene Konstanten versteckt und die deutlichen Unterschiede kommen erst in Großendatenbereichen (bin mir nicht sicher ob 1000 Datensätze da schon reichen).
Zudem wirkt auf den ersten Blick deine Mergesortimplentierung ein wenig in-place, dass wäre zwar schön, nur ist der Mergesort kein Algorithmus der das beherrscht. Das erfüllen zwar Algorithmen wie Insertion-, Bubble- und vorallem Quicksort, nur halt gerade der Mergesort nicht. Wenn du eine schnelle Implementierung dadurch erreichen möchtest, dass du nur Indizes kopierst, es geht schöner. Du kannst einfacher mit Pointern arbeiten. Ein Zeiger auf ein Record ist immer 4 Byte groß (oder anders gesagt entspricht der Registerbreite -> ist optimal). Wenn du in deinem Array nur die Zeiger auf die Datensätze sortierst, kannst du mittels Derefenzierung problemfrei auf die enthaltenen Daten zugreifen und verschiebst gleichzeitig nicht unnötig viele Daten im Speicher.
Ansonsten würde ich dir Raten auch wirklich dynamische Arrays zu verwenden und nicht die Größe auf 1000 Datensätze fest zu legen. Die kannst du einfach verwenden:
Delphi-Quellcode:
var dynArray : Array of TDeinPointer; // dyn. Array vom Typ TDeinPointer
begin
// die Länge dyn. zuweisen (natürlich an geeigneter Stelle!)
setLength(dynArray, right - left);
// irgendwas mit dem Array machen
....
// aufräumen
finalize(dynArray);
setLength(dynArray, 0);
end;
Bei dem Irgendwas mit dem Array machen, ist es halt wichtig, dass du nicht versuchst in-place zu arbeiten. Das heißt, dein Eingabearray wird nicht direkt weiterverwendet. Dies ist wegen dem Mischen leider nicht möglich. Du mussst wirklich ein neu erzeugtes Array zurückgeben (gerade hier liegen viele Nachteile im Mergesort). Effizienter ist und bleibt da halt der Quicksort (mehr als nur im Mittel) und eigentlich müsste auch der Heapsort (weil in-place) etwas flinker sein. Aber da bin ich mir wieder nicht sicher, assymptisch laufen die alle (im MIttel) gleich.
Gruß Der Unwissende