MergeSort Implementation, optimierungsbedraf?

[Jonas Shinaniganz]

Okay also Ich habe die SetLength Befehle gelöscht und setze die länge nur einmal.

Da mein Hilfsarray durch die Länge in der letzten Forschleife auchnoch geregelt hat welche Werte übertragen werden musste Ich das mit dem I erschlagen.


SetLength(ArrayResult, High(IntArray) + 1);

Delphi-Quellcode:

 
for I := I - 1 downto 0 do
begin
  IntArray[StartGO + I] := ArrayResult[I];
end;

Die Abfrage am Anfang habe Ich angepasst und jetzt darf der Startwert nicht mehr größer sein als der Endwert. Finde Ich auch sehr sinnvoll.

if ((Ende - Start > 0) and (Ende > Start)) then (Ende - Start > 0) ist besser als mein (High(IntArray), Hier soll ja nicht nur abgedeckt sein ob der Array der übergeben wurde 1 oder weniger Elemente hat sonder auch die Bereichssortierung berücksichtigt werden, Sodass bei einem Bereich von 1 oder weniger nichts passiert.

Das I := 0; nahe dem Ende ist überflüssig. Stimmt.

Zitat:

Weiterhin würde ich refaktorisieren, d.h. das Mergesort in seine logischen Bestandteile aufteilen:
1. Divide
2. Sort parts
3. Recombine (aka Merge)

Grundsätzlich finde Ich das sehr gut... das Motto Seperation of Concerns bei Klassen und das Divide and Conquer Prinzip sind gut.

Mein Gefühl sagt mir hier keine Trennung vorzunehmen. Manchmal ist es mit kurz und simpel an einem Ort auch getan.

Die Begin und Ends in 1-zeiligen Anweisungen füge Ich immer bei.
Der Lesbarkeit halben. Finde es so übersichtlicher. Sie wegzulassen ist vielleicht auch gut für die Lesbarkeit... hauptsache man macht es einheitlich. Habe es unten bei der Forschleife vergessen und noch hinzugefügt.


Eine Warnung auszugeben, falls der Merge-Sort nicht effizient ist, dazu vielleicht ein Vorschlag für einen anderen Algo wäre cool.

Zitat:

Performancetechnisch könnte man die alte Weisheit aufgreifen, das z.B. ein Straight Insertion Sort für kleine Listen schneller ist. Dann würde man dieses Verfahren anwenden, wenn Ende-Start < 20 ist. Wobei "20" ein eher willkürlicher Wert ist, welchen es zu verifizieren gilt. Es könnte auch andere Verfahren geben (außer SIS), die für kleine N besser sind.

Da müsste man dann noch weiter Überlegen und einen Wert verifizieren. Auch ein guter Vorschlag vielleicht schaffe Ich es ja bis morgen.

Zitat:

Was meinst Du mit 'Optimierungsbedarf'?

genau sowas. Danke