Arbeitsweise

Wie schon durch das Mischen erläutert, führt der MergeSort genau diese Operation durch. Zuvor aber, teilt er die zu sortierende Datenmenge in entsprechende Teilmengen auf, und zwar so lange bis, jede Teilmenge aus nur einem Element besteht, danach mischt er zwei Mengen zu einer zusammen. Dies wiederholt der Algorithmus so lange, bis er alle Teilmenge zu einer einzigen sortierten Menge gemischt hat.

Teile
Falls die zu sortierende Menge nicht klein genug ist, wird diese geteilt und die entstehenden Teilmengen mit dem MergeSort sortiert.
Hersche
Nun werden die (kleinen) Teilmengen für sich sortiert. Hier liegen sie schon sortiert vor, da sie aus nur einem Element bestehen.
Kombiniere
Durch Mischen der Teilmengen werden diese zu grösseren zusammengefügt, und zwar ist die daraus resultierende Menge sortiert.

Ein Beispiel soll die Arbeitsweise des MergeSorts auf einer Datenmenge
{ 18, 35, 22, 10, 12, 25, 13, 31, 1, 8, 0, 16, 4 } verdeutlichen, wobei das Mischen der Elemente durch die oben dargestellte merge-Funtion erledigt wird. Jede Stufe der folgenden Tabelle zeigt die entsprechenden Teilmengen nach dem Mischen. Das heisst es werden die zwei zuletzt behandelten Teilmengen kombiniert.

18 35 22 10 12 25 13 31 1 8 0 16 4
18 35                      
    10 22                  
10 18 22 35                  
        12 25              
            13 31          
        12 13 25 31          
10 12 13 18 22 25 31 35          
                1 8      
                    0 16  
                0 1 8 16  
                0 1 4 8 16
0 1 4 8 10 12 13 16 18 22 25 31 35

Nächste Seite  Aufwärts  Vorherige Seite  Inhalt 


Nächste Seite: Implementierung Aufwärts: MergeSort Vorherige Seite: Mischen   Inhalt

2002-05-09