MergeSort Implementation, optimierungsbedraf?

[Iwo Asnet]

Zitat von Jonas Shinaniganz:

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.

Das hast Du falsch verstanden. Du kannst deine Implementierung einfach in 5 Einzelroutinen unterteilen, die genau eine Sache machen:
1. Liste in zwei Teile teilen
2. Untere Teilliste sortieren
3. Obere Teilliste sortieren
4. Beide Teillisten in eine neue Liste kopieren (sodaß die neue Liste sortiert ist)
5. Temporäre Liste in die Originalliste zurückkopieren

Der Code steht ja schon da, nur ist er hintereinander in einer Methode. Es wäre von der Ästhetik und Lesbarkeit optimaler, hier zu refaktorisieren.

[Laser]

Moin,

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

[Delphi-Laie]

Zitat von Laser:

vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?

Parallelisierung ist bei Mergesort m.E. schwieriger als z.B. bei Quicksort, weil die Threads "synchronisiert" werden müssen, und zwar in der Weise, daß erst, wenn die beiden Teilsortierungen fertig sind - dann aber ohne Verzug - beide Teilmengen verschmolzen werden müssen, während hingegen bei Quicksort die Sortierungen der Teilmengen unabhängig voneinander weiterwerkeln können. Aber mit den richtigen Konzepten (Metaphoren? Keine Ahnung) ist eine solche Synchronisierung sicher möglich.

Am Mergesort selbst läßt sich zum einen die Rekursion beseitigen, aber der Algorithmus als solcher bleibt dabei bestehen, nur der Stackbedarf wird vermieden.

Die eigentliche Optmierung des Mergesorts besteht allerdings darin, von einem Tiefen- zu einem Breitenalgorithmus überzugehen, konkret zum sog. Natura Mergesort, das bei entsprechender Implementation in der Lage ist, Vorsortierungen auszunutzen und ggf. auch invertierte Teilfolgen "richtigherum zu invertieren".