Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


12. Mergesort



Kenngrößen der Leistungsfähigkeit

Eigenschaft 12.1 Mergesort erfordert für das Sortieren einer beliebigen Datei aus N Elementen ungefähr N lg N Vergleiche.

In den obigen Implementationen erfordert jedes Mischen »M mit N« M + N Vergleiche (die Anzahl könnte um eins oder zwei variieren, je nachdem, ob Marken benutzt werden). Nun werden für Bottom-Up-Mergesort lg N Traversierungen verwendet, von denen jede ungefähr N Vergleiche erfordert. Für die rekursive Variante wird die Anzahl der Vergleiche durch die standardmäßige rekurrente Beziehung für das Prinzip »Teile und Herrsche« MN = 2MN/2 + N beschrieben, mit M1 = 0. Aus Kapitel 6 wissen wir, daß diese die Lösung MN rund N lg N hat. Diese Argumente sind beide exakt gültig, wenn N eine Zweierpotenz ist; es wird dem Leser als Übung überlassen zu zeigen, daß sie für allgemeines N ebenso gelten. Darüber hinaus erweist es sich, daß sie auch im durchschnittlichen Fall gelten. w.z.b.w.

Eigenschaft 12.2 Mergesort erfordert zusätzlichen Speicherplatz, der zu N proportional ist.

Dies ist von den Implementationen her klar, obwohl Schritte unternommen werden können, um die Auswirkungen dieses Problems abzuschwächen. Wenn die zu sortierende »Datei« eine verkettete Liste ist, tritt das Problem natürlich nicht auf, da der »zusätzliche Speicherplatz« (für die Verkettungen) aus einem anderen Grund bereits vorhanden ist.

Für Felder bemerken wir zunächst, daß es einfach ist, ein Mischen »M mit N« vorzunehmen und dabei nur für das kleinere der beiden Felder zusätzlichen Speicherplatz zu benutzen (siehe Übung 2). Dadurch halbiert sich der Platzbedarf für Mergesort. In Wirklichkeit ist es möglich, noch viel mehr zu erreichen und Mischoperationen »am Ort« vorzunehmen, obwohl sich das in der Praxis meist nicht lohnt. w.z.b.w.

Eigenschaft 12.3 Mergesort ist stabil.

Da alle Implementationen nur während der Mischoperationen wirklich Schlüssel bewegen, muß lediglich überprüft werden, ob die Mischoperationen selbst stabil sind. Doch das ist leicht zu zeigen: Die relative Position gleicher Schlüssel wird durch den Prozeß des Mischens nicht verändert. w.z.b.w.

Eigenschaft 12.4 Mergesort ist gegenüber der ursprünglichen Reihenfolge der Eingabedaten unempfindlich.

In unseren Implementationen bestimmen die Eingabedaten nur die Reihenfolge, in der die Elemente bei den Mischoperationen verarbeitet werden, so daß diese Behauptung im wörtlichen Sinne wahr ist (mit Ausnahme gewisser Unterschiede, die davon abhängen, wie die if-Anweisung übersetzt und ausgeführt wird, was vernachlässigbar sein dürfte). Andere Implementationen des Mischens, die einen expliziten Test beinhalten, ob die erste Datei erschöpft ist, können zu etwas größeren Unterschieden in Abhängigkeit von den Eingabedaten führen, die jedoch nicht zu groß sind. Die benötigte Anzahl von Durchläufen hängt eindeutig nur von der Größe der Datei ab und nicht von ihrem Inhalt, und jeder Durchlauf erfordert mit Sicherheit etwa N Vergleiche (in Wirklichkeit N - O(1) im Durchschnitt, wie weiter unten erläutert wird). Doch der ungünstigste Fall entspricht ungefähr dem durchschnittlichen Fall. w.z.b.w.

Abbildung 12.4 zeigt Bottom-Up-Mergesort in seiner Anwendung auf eine Datei, die ursprünglich in umgekehrter Reihenfolge angeordnet ist. Es ist interessant, diese Abbildung mit Abbildung 8.9 zu vergleichen, welche Shellsort bei der Ausführung der gleichen Operation zeigt.

Abbildung 12.4
Abbildung 12.4 Mergesort einer in umgekehrter Reihenfolge geordneten Permutation.

Abbildung 12.5 zeigt eine weitere Darstellung der Wirkungsweise von Mergesort beim Sortieren einer zufälligen Permutation zum Vergleich mit ähnlichen Veranschaulichungen in früheren Kapiteln. Insbesondere weist Abbildung 12.5 eine verblüffende Ähnlichkeit mit Abbildung 10.5 auf: In diesem Sinne ist Mergesort die »Transponierung« von Straight Radix Sort!

Abbildung 12.5
Abbildung 12.5 Mergesort einer zufälligen Permutation.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]