Mergesort - godx.de

Mergesort gehört auf Grund der vorhersagbaren, stabilen Laufzeit, der möglichen stabilen Sortierung und der möglichen Parallelisierung zu den beliebten Sortierverfahren. Die Anzahl der nötigen Schiebeoperationen liegt bei n*log2(n), die Anzahl der maximal benötigten Vergleiche kann durch die Summe der log(n) Durchläufe von den Zweiterpotenzen des Durchlaufs minus Eins errechnet werden.

Beispiel (Quellcode): mergesort.cpp
Download (Quellcode): mergesort.zip

Aufteilung des Feldes

Aufteilung durch Mergesort Bei der rekursiven Variante ist es möglich, das Eingangsfeld immer zu halbieren (linke und rechte Hälfte), bis nur zwei oder weniger Elemente zu Verfügung stehen. Die maximale Rekursionsebene liegt bei log2 der Elementgesamtanzahl. Bei Beispielhaften 65536 Elementen also nur 16 Ebenen.

Bei der nicht rekursiven/iterativen Variante, wird direkt mit der kleinstmöglichen Teilfeldgröße (zwei Elemente) begonnen und die Teilfeldgröße in jedem Durchgang erhöht/verdoppelt. Ebenso wie bei der rekursiven Variante beträgt die Anzahl der Durchgänge log2 der Elementgesamtanzahl. (Siehe Bild)

Welche Variante auch die Teilfelder erzeugt, es ist nur nötig die Positionen und ggf. Längen der Teilfelder aus dem Gesamtfeld zu ermitteln (je nach Sprachmöglichkeiten). Wichtig daran ist, dass das Teilfeld nur maximal eine Schnittposition hat. Die Schnittposition bestimmt das Element, welches "kleiner" als das Vorhergehende ist. Dies ist im einfachsten Fall, bei zwei Elementen, immer gegeben.

Es ist möglich, vor der Verarbeitung, durch einen einmaligen Vergleich jedes Elements mit dessen Nachbarn festzustellen, ob eine Schnittposition vorliegt oder nicht (Natürliches Mergesort). Hierdurch kann erkannt werden, ob ein schon sortiertes (Teil-)Feld vorliegt und der Vorgang wird wesentlich beschleunigt.

Dadurch, dass Teillisten keine Vergleiche mit anderen Teilfelder durchführen, kann dieser Prozess parallelisiert werden. Zum Beispiel ist es möglich große Felder auf mehreren Prozessorkernen oder gar von anderen Rechnern durchführen zu lassen. Nur bei den letzten Durchgängen ist dies nicht möglich, wenn die Anzahl der Teilfelder kleiner der Anzahl der Teilprozesse ist.

Sortieren eines Abschnittes

Zusammenführung durch Mergesort Sobald die Teilfelder bestimmt wurden, werden diese über die Schnittposition zusammengeführt. Dabei wird bei beiden Teilen jeweils mit dem ersten Element angefangen. Das kleinere der Beiden wird in das Ausgabefeld geschrieben. (Siehe Bild) Beim nächsten Durchlauf kommt das nächste Element des gleichen Teils dran.

Wenn ein Teil keine Elemente mehr besitzt, kann der andere Teil direkt zum Ausgabefeld hinzugefügt werden, da keine weiteren Vergleichsoperationen notwendig sind.

Falls als Ausgangsbasis ein Vector/Array verwendet wurde, empfiehlt es sich ein Hilfsfeld zu nehmen, was als Ausgabefeld für die Zwischenschritte dient. Eine Verschiebung der Elemente im Vector/Array ist je nach Feldgröße und Objekttypen zu Zeitintensiv und auch das Mergesort selbst wird dann langsam. Für verkettete Listen besteht, dieses Problem grundsätzlich nicht, da Elemente dort schnell eingefügt und gelöscht werden können.

Die Anzahl der maximal nötigen Vergleichsoperationen ist gleich der Teilfeldlänge minus Eins. Da beim Ende eines Teilfeldes nicht weiter verglichen wird, fällt es oft etwas unter das Maximum.

Durch den Beispielcode

Der Beispielcode, enthält eine Templateklasse (C++), die zwei wesentliche Methoden besitzt:

die Sortierungsfunktion
```
void Sort(std::vector<_TYPE>& toSort)
```
```
19
```
Feld welches sortiert werden soll. Hierbei wird das Eingangsfeld verändert.
die Vergleichsfunktion
```
int Compare(const _TYPE& left, const _TYPE& right)
```
```
54
```
Zwei Elemente werden miteinander verglichen. Dies wird durch die Sortierungsfunktion aufgerufen und muss für den jeweiligen Objekttyp spezialisiert werden.

Rückgabewerte:
- < 0 = Element ist "kleiner"
- = 0 = Element ist gleich
- > 0 = Element ist "größer"

Codeanmerkungen

Der Code erzeugt ein Hilfsfeld mit
```
std::vector<_TYPE> helper(toSort.size());
```
```
21
```
um keine Elemente zu überschreiben, bevor sie zur Vergleichsfunktion gelangen. Danach nach jedem Durchgang, wird das Hilfsfeld zurück in das Eingangsfeld kopiert durch
```
for(size_t nCopy=0; nCopy<toSort.size(); nCopy++)
   toSort[nCopy] = helper[nCopy];
```
```
49
50
```
std::string ist hier durch Templatespezialisierung angeben.

Die Ausrufparameter des Programms werden als sortierende Elemente benutzt:

std::vector<std::string> arrayToSort;
for(int n=1; n<argc; n++)
   arrayToSort.push_back(argv[n]);

78
79
80

So ergibt

./mergesort dies ist ein mergesort test und gleichzeitig ein beispiel

die Ausgabe

Mergesort test...

std::string:
 sorted 9 elements:
   1. beispiel
   2. dies
   3. ein
   4. ein
   5. gleichzeitig
   6. ist
   7. mergesort
   8. test
   9. und