Sortieralgorithmen

Entsprechend der Aufgabenstellung wurden sämtliche Sortieralgorithmen so angepasst, dass sie „Strings“ sortieren. Es erscheint einfach sinnvoller in Suchmaschinen Wörter und Sätze behandeln zu können. In den Abbildungen zur Verdeutlichung der Funktionsweise werden dagegen Zahlen sortiert, da dies leichter verständlich und übersichtlicher ist.
Die Funktionen werden mit unterschiedlichen Parametern aufgerufen. Das dynamische Stringfeld wird an „*feld“ übergeben. „n“ steht immer für die Anzahl der Elemente und „hi“ für das grösste.

Bubble Sort

Hierbei handelt es sich um einen der bekanntesten und auch simpelsten Sortieralgorithmen. Stellt man sich das Vertauschen bildlich vor, hat man den Eindruck, als ob die zu sortierenden Daten wie Luftblasen im Wasser aufsteigen, daher auch der Name Bubble Sort.

Vertausche das aktuelle Element an erster Stelle solange mit kleineren auf der rechten Seite, bis das Ende der Liste erreicht ist. Fahre dann mit dem Element an zweiter Position fort, usw.

Dies soll noch einmal ausführlich erklärt werden. Die Datenliste, hier ein Array in linearer Anordnung, wird beginnend beim ersten Index bis zum letzten durchlaufen, dabei wird das erste Element mit jedem weiteren verglichen. Ist der Vergleich positiv, also der erste Wert der grössere, werden beide vertauscht. Nun wandert der kleinere Wert nach links an die erste Position. Nach diesem, dem ersten, Durchlauf ist das kleinste Element gefunden und steht sortiert am richtigen Platz.
Um auch den Rest der Daten zu sortieren, wird die gesamte Prozedur wiederholt, mit dem Unterschied, dass die verbleibenden Elemente auf der rechten Seite mit dem Wert an zweiter Stelle verglichen werden. So wird nach jedem Durchlauf durch die Liste das kleinste Element ausfindig gemacht und hinter das noch kleinere, aus dem vorherigen Ablauf gefundene Element, gesetzt.
Es ergibt sich so eine um eins abnehmende Anzahl der Vergleiche pro Durchlauf durch das Array. Der Vergleich eines Datums mit sich selbst, ist bedingt durch die Umsetzung des Algorithmus ausgeschlossen.

In der Abbildung wird die Funktionsweise von Bubble Sort anhand eines Beispiels verdeutlicht. Hier wird die Zahlenfolge 6 4 8 2 sortiert. Die farbige Hervorhebung der Zahlen soll die aktuell behandelten Positionen verdeutlichen. In den Schritten 1 bis 3 ist sehr gut zu sehen, wie der jeweils kleinere Wert der Liste (hier die 2) nach vorne wandert, bzw. „aufsteigt“.

Eine an das bestehende Problem angepasste Implementation des Algorithmus zeigt Quellcode 1. Übergeben wird eine Referenz eines dynamischen Arrays (*feld), welches die zu sortierenden Strings enthält, an die Funktion. Ebenso muss die Grösse (n) des Arrays im Aufruf angegeben werden.

Insertion Sort

Im Vergleich zu Bubble Sort handelt es sich bei Insertion Sort um einen wesentlich leistungsfähigeren Algorithmus und dennoch zählt er ebenfalls zu den elementaren Sortierverfahren. Seine Umsetzung ist schon etwas komplizierter.

Gehe das Array vom Anfang bis zum Ende durch, vergleiche den aktuellen Wert, rückwärtslaufend bis zum ersten Index, mit allen links von ihm liegenden Elementen. Sind diese grösser als das aktuelle Element, schiebe sie jeweils um eine Position nach rechts, ansonsten füge den aktuellen Wert an der zuletzt bearbeiteten Position ein.

Um das Verfahren verständlicher zu machen, kommt nun die ausführlichere Erklärung. Das Array wird beginnend beim zweiten Feld bis zum Ende durchlaufen. Dabei wird jedesmal das Element in einer Hilfsvariablen zwischengespeichert. Eine Schleife, die nun rückwärts vom linken aktuellen Feld bis zum Anfang läuft, sorgt für einen Vergleich des abgelegten Wertes mit jedem der linken. Bei einem positiven Vergleich wird das Datum genommen und in das Feld rechts von ihm kopiert. Dieses Kopieren wird solange wiederholt, bis der Vergleich negativ ausfällt. Nach mindestens einem Kopiervorgang ist der letzte Wert doppelt vorhanden. Doch dieser verschwindet nun, da der Vergleichswert, der in einer Hilfsvariablen liegt, dort abgelegt wird. Diese Prozedur erinnert sehr stark an das Sortierverhalten von Kartenspielern, die sich jede Karte merken und die kleineren links an der richtigen Stelle einfügen. Im Insertion Sort wird dagegen das kleinere Element nicht wirklich eingefügt. Es werden nur alle grösseren Daten um eine Position nach rechts verschoben, so dass ein freier Platz einsteht, der auch gleich vom Vergleichswert in der Hilfsvariablen beansprucht wird.

Shell Sort

Der nun vorgestellte Shell Sort Algorithmus, benannt nach seinem Erfinder Shell, stellt für viele Programmierer ein Kompromiss aus Einfachheit und Geschwindigkeit dar. Obwohl er auf dem gerade besprochenen Insertion Sort basiert, ist ein Vertauschen von Elementen, die weit auseinander liegen, mit einer deutlich geringeren Anzahl an Operation möglich.

Teile die gesamte Liste in mehrere gleich grosse auf, sortiere die Daten der einzelnen Listen nach dem Insertion Sort Verfahren. Nach Beendigung beginne von vorne, mit dem Unterschied, dass die Anzahl der Elemente pro Liste immer kleiner werden.

Der Grundgedanke ist eine h-Sortierung der Datenliste. Eine Liste ist dann h-sortiert, wenn jedes h-te Element einer kleineren Gruppe zugehört, entsprechend das h+1-te Element einer weiteren, usw. Mit anderen Worten gesagt, eine Liste besteht aus h unabhängigen Listen. Um den Algorithmus einfach zu halten, wird die Liste nur logisch aufgeteilt. Sollen die Daten der ersten Gruppe gelesen werden, liest man das erste Element und von da an immer im Abstand h. Für die zweite Gruppe wird analog am nächsten Feld beginnend gelesen. Entscheidend für die Geschwindigkeit ist ein richtig gewähltes h, welches in Form eines Arrays fest im Quellcode implementiert sein muss. Aus Untersuchungen weiss man, dass es keine perfekte h-Sortierung gibt, deshalb findet man häufig unterschiedliche Zahlenfolgen. Im Beispielcode wird folgende verwendet: ..., 336, 112, 48, 21, 7, 3, 1. In Worten gesagt, die Datenliste wird zuerst so unterteilt, dass jeder 336-te Wert in der gleichen Gruppe landet, dann jeder 112-te, usw. Denkbar ist auch jede andere Abfolge, nur dürfen die Abstände nicht zu klein gewählt werden, da der Effekt des Shell Sort sonst verloren geht.
Nun wurde schon viel über die h-Sortierung und wenig über den eigentlichen Algorithmus erzählt. Im Grunde genommen arbeitet er wie Insertion Sort, mit dem Unterschied, dass die zu vergleichenden Elemente nicht immer direkte Nachbarn sein müssen. Dies ergibt sich natürlich durch das h , welches den Abstand der beiden Elemente widerspiegelt.
Stellt man sich die Liste als Tabelle vor, stellt jede Spalte eine Gruppe dar. Sortiert werden dann die Elemente der einzelnen Spalten nach dem Insertion Sort Prinzip. Somit wandern die kleinsten Elemente jeder Gruppe in die erste Zeile. Dies wird so lange wiederholt bis jede Gruppe nur noch ein Element enthält. Es folgt dann der letzte Sortiervorgang, der mit seiner Schrittweite von eins also h=1 exakt dem Insertion Sort entspricht.
Die obere Grafik gibt den Sortiervorgang der Zahlen 6-2-4-9-7-0-3-8-5-1 wieder. Die erste Teilung wird in fünf Gruppen vorgenommen, dann werden diese einzeln sortiert. Aus diesem erstsortierten Array werden nun drei Gruppen gebildet, logischerweise fallen sie deutlich grösser aus. Auch hier wird wieder so sortiert, dass die kleinen Werte an den Anfang der Gruppe wandern. Setzt man die sortierten Gruppen zusammen, ergibt sich folgende Zahlenfolge: 0-1-4-3-2-6-5-8-9-7. Obwohl die Reihenfolge noch nicht ganz stimmt, kann man schon gut erkennen, dass der überwiegende Teil an kleinen Zahlen im vorderen Bereich der Liste anzufinden ist. Abschliessend kommt das einfache Insertion Sort (ohne h-Sortierung), und bringt die Zahlen in die endgültige sortierte Reihenfolge. Da der Vorgang aus dem vorherigen Kapitel bekannt sein sollte, wird auf den letzten Vorgang nicht mehr eingegangen.
Die Umsetzung des Shell Sort Algorithmus zeigt der unten folgemde Quellcode. Auffällig ist auch das Array „cols“, welches einige h‘s für die Gruppenbildung enthält.

Quick Sort

Mit Quick Sort wird ein völlig neues Konzept beschrieben, dem Divide-and-Conquer. Übersetzt Teile-und-Herrsche, gibt es schon den grundlegenden Gedanken wieder. Eine Datenmenge wird so in zwei Teilmengen zerlegt, dass die eine die kleineren und die andere die grösseren Elemente enthält. Beide Teilmengen werden wieder nach dem Divide-and-Conquer bearbeitet.
Der Einfachheit halber wird Quick Sort als Rekursion implementiert, d.h. es ruft sich selbst so lange auf, bis bestimmte Bedingungen erfüllt sind. Leider wirkt die Umsetzung des Algorithmus auf den ersten Blick sehr kompliziert, doch anhand Abbildung 4 sollte der Ablauf gut erkennbar sein.

Wähle ein Pivot-Element, dann teile die Liste in zwei Gruppen auf. Werte, die grösser/gleich dem Pivot sind, bringe in die rechte Gruppe, kleinere/gleiche in die linke. Rufe die Funktion erneut auf, um die Teilgruppen analog zu bearbeiten.

Beim Aufruf der Funktion wird wie gewohnt das zu sortierende Feld als Referenz (*feld) und die Grösse (hi) übergeben. Neu ist die Übermittlung der Position des ersten Feldes (lo). Am Anfang wird das mittlere Feld ermittelt, sein Inhalt wird zwischengespeichert und dient als Referenzwert (Pivot) für die Vergleichsoperationen. Es könnte genauso gut ein anderes Feld als Pivot verwendet werden, doch es hat sich ergeben, dass das mittlere sich besonders günstig auf das Sortierverhalten auswirkt.
Um die zu tauschenden Objekt zu ermitteln, bedient man sich zweier Zeiger i und j, die von links bzw. rechts zur Mitte laufen. Zeiger i wird so lange verschoben, bis ein Element gefunden ist, das grösser oder gleich dem Referenzwert ist. Ebenso verfährt man mit j, nur dass das Element kleiner oder gleich sein soll. Nachdem noch geprüft wurde, dass die Zeiger nicht über die Mitte hinaus gelaufen sind, werden die Daten an den durch i und j ermittelten Positionen getauscht. Dieser Vorgang des Verschieben der Zeiger wird solange durchgeführt, bis ein Tauschen nicht mehr zum richtigen Ergebnis führt, also i und j sich überschneiden. Ist dies der Fall, wird geprüft, ob links vom Zeiger j noch Elemente stehen. Wenn ja, erfolgt der rekursive Aufruf der Funktion mit geändertem hi-Paramter, ihm wird j zugewiesen. Die letzte Abfrage wird auch mit i gemacht, wobei hier noch Werte rechts von dem Zeiger gesucht werden. Beim Aufruf bleibt hi konstant, lo wird nun i zugewiesen.
Auch wenn bei jedem erneuten Aufruf das gesamte Datenfeld übergeben wird, verkleinern sich die Grenzen, in denen der Sortiervorgang ausgeführt wird. Dies ist auch nur deshalb möglich, da vor jeder erneuten Rekursion ein oder zwei sortierte Elemente an den richtigen Platz bewegt wurden und diese dann nicht mehr berücksichtigt werden müssen.
Die Implementation des Quick Sort zeigt der Quellcode unten.

Heap Sort

Heap Sort bedient sich eines völlig neuen Konzeptes. Es erstellt aus einem Datenarray einen binären Baum, der zu einem Heap umgewandelt wird. Damit ist die Wurzel eindeutig das grösste Element und kann dem Heap entnommen werden. Der verbleibende Baum muss nun wieder zum Heap gemacht werden, um das nächste, das zweitgrösste, Datum, zu ermitteln.

Interpretiere das Array als binären Baum, dann mache aus ihm einen Heap. Tausche die Wurzel mit dem letzten Blatt und wiederhole die Heapumwandlung, ohne das jeweils letzte Blatt zu berücksichtigen. Die aufwärts sortierte Datenfolge kann dem Array sofort entnommen werden.

Vorab sollten noch einige grundlegende Begriffe erklärt werden.
Ein binärer Baum ist eine Datenanordnung, die ausgehend von einer Wurzel immer zwei Nachfolger mit jeweils einem weiteren Datenfeld besitzt. Die einzelnen Datenfelder werden Knoten genannt, die Verbindungen zwischen ihnen Kanten. Ausnahmen bilden hier die Wurzel und die Blätter. Letztere sind die abschliessenden Elemente, von denen keine Kanten ausgehen, also keine Nachfolger haben.
Beginnt man den binären Baum zu sortieren, und zwar mit der Bedingung, dass die grössten Elemente Richtung Wurzel stehen, spricht man von einem Heap. Sein Aufbau ist dem Baum identisch. Eine Zwichenstufe bildet der Almost-Heap, dort besitzen alle Knoten und Blätter die Heapeigenschaft. Nur die Wurzel hat grössere Nachfolger.
Der binäre Baum wird normalerweise mit Hilfe von Pointer aufgebaut, die das Objekt und zwei weitere Zeiger mit sich führen. Wobei jeder der Zeiger auf ein neues Objekt zeigt. Da es hier gar nicht notwendig ist, den Baum als solchen darzustellen, greift man einfach nach einem bestimmten Verfahren auf das Array zu. Verdeutlicht wird das Prinzip der Umwandlung vom Array in den Baum, durch untenstehende Abbildung.

Nun stellt sich allerdings die Frage, wie man mit wenig Aufwand aus dem binären Baum einen Heap bekommt. Der Gedanke ist der, dass man jeden Knoten als „Wurzel“ ansieht und auf die Heapeigenschaft hin untersucht. Umgesetzt wird es, indem man eine Wurzel mit seinen höchstens zwei Nachfolgern nimmt, und prüft, ob einer der beiden grösser als die Wurzel ist. Wenn dies der Fall ist, werden beide Elemente ausgetauscht. Es muss noch überprüft werden, ob die Nachfolger immer noch die Eigenschaft des Heaps haben.
Die weiter unten folgende Grafik verdeutlicht sehr anschaulich das Entstehen des Heaps. Die grauen Rechtecke sollen immer den Teilbaum angeben, der gerade zum Heap gemacht wird. Hierbei ist die Wurzel immer das oberste Feld im Rechteck. Gerade in den letzten beiden Schritt erkennt man, dass die 7 an die zweite Stelle rutscht. Die Wurzel des gesamten Baumes ist nun ein Heap, doch der linke Knoten, eben diese 7 verliert die Eigenschaft des Heaps, nun wird der Baum solange in Richtung Blätter abgetastet, bis dieser Wert an der richtigen Stelle steht und der ganze Baum zum Heap geworden ist.

Zur Erzeugung des Heaps werden gleich zwei Funktionen benötigt, buildheap und downheap. In downheap kann jeweils nur ein vorgegebener Teilbaum (die grauen Rechtecke) und nötigenfalls die Nachfolger zum Heap gemacht werden. Um nun aber den gesamten Baum umzuordnen, gibt es die Funktion buildheap, die unten beginnend jeden Knoten bis zur Wurzel durchläuft. Dabei wird jeder Knoten einzeln durch Aufruf von downheap bearbeitet. Das Ergebnis ist ein binärer Baum mit der Eigenschaft eines Heaps, der nach wie vor in dem Array abgebildet ist.

Zu guter Letzt fehlt noch der eigentliche Sortieralgorithmus. Umgesetzt ist er im folgenden Quellcode, welcher bis auf eine kleine Schleife und Funktionsaufrufe nicht viel enthält.

Die wichtigste Aufgabe ist das wiederholte Aufstellen eines Heaps auf Grundlage des binären Baumes. Ist dies erreicht, bedeutet es, dass das grösste Element der Datenliste in der Wurzel steht. Dieses Element wird nun nur noch mit dem letzten Blatt vertauscht. Dadurch ergibt sich unweigerlich ein Almost-Heap, da die Wurzel nun nur in Ausnahmefällen die Heapeigenschaft erfüllt. Vernachlässigt man nach jedem Tausch der Wurzel das letzte Blatt, baut sich allmählich von hinten eine sortierte Liste auf.

Merge Sort

Auch dieser Sortieralgorithmus basiert auf dem Divide-and-Conquer-Prinzip. Die zu sortierenden Datenmengen werden erst in kleinste Einheiten geteilt (Divide), um dann sortiert (Conquer) zu werden. Wie der Name des Verfahrens schon sagt, wird der Vorgang des Sortierens durch Mischen (Merge) der einzelnen Einheiten vollzogen.

Teile die Daten in zwei gleich grosse Teile. Fahre solange fort, bis nur noch ein Element pro Teilmenge vorhanden ist. Mische die jeweils letzten zwei Teile so, dass die kleineren Daten an die linke Seite wandern.

Der gesamte Algorithmus besteht eigentlich nur aus einem simplen Mischverfahren und einer Rekursion, die das Datenarray aufteilt, um es dann zu verarbeiten. Um die Funktion leichter zu verstehen, sei in der nächsten Grafik das Funktionsprinzip dargestellt. In der Abbildung entsteht der Eindruck einer parallelen Behandlung der Teilelemente, was natürlich nicht der Fall ist. Diese Form der Darstellung wurde nur aus Gründen der Übersicht gewählt.

Eine Zahlenfolge mit acht Einträgen wird hier auf einfachste Weise sortiert. Als erstes wird diese halbiert, somit ergeben sich zwei Datenarrays mit je vier Elementen. Am Ende stehen praktisch acht Teilmengen mit genau einem Element. Nun beginnt der eigentliche Sortiervorgang. Durch Mischen (Merging) von jeweils zwei gleich grossen Feldern, unter der Voraussetzung, dass die kleineren Elemente nach links wandern, entsteht Stück für Stück eine sortierten Reihe. Anders formuliert entsteht nach jedem Mischvorgang (Mergeing) eine doppelt so grosse Zahlenfolge, die mit einer ebenso langen vermischt wird.
Leider weicht die Verdeutlichung in der Grafik ein wenig vom tatsächlichen Ablauf des Merge Sort ab. Es werden eben nicht erst alle Teilmengen gebildet, um diese dann zu mischen. Die Implementation sieht es vor, dass das vorhandene Datenarray so lange geteilt wird, bis nur noch zwei Elemente vorhanden sind. Dagegen liegen die restlichen noch in der alten Form vor, schliesslich wurden sie noch gar nicht behandelt. Die beiden ersten Daten werden aber jetzt schon vermischt und bilden praktisch die erste, wenn auch noch nicht endgültige, sortierte Einheit. Dann werden die nächsten beiden Elemente der darüberliegenden grösseren Teilmenge auf die gleiche Weise behandelt. Sie werden erst geteilt und dann gemischt. Erreicht die Teilmenge die Grösse der vorangegangenen fertigen Menge, werden diese wiederum zusammen gemischt.
Zur Verwirklichung des Algorithmus gehören zwei Funktionen mit unterschiedlichen Aufgaben: merge und mergesort. In merge werden die übergebenen Datenelemente vermischt und in die richtige Reihenfolge gebracht. Mergesort ist dagegen für das Unterteilen des Arrays zuständig, und ruft bei Bedarf die merge-Funktion auf.
In Quellcode weiter unten ist die eben angesprochene Funktion umgesetzt. Das Datenfeld wird von der aufrufenden Funktion mit den neuen Grenzen lo und hi übergeben. Somit sind die aktuellen Elemente eindeutig bestimmt. Zur Hilfe wird ein neues dynamisches Array mit der neuen Länge angelegt. Die Elemente des übergebenden Feldes werden nun in das neue kopiert. Zu beachten ist, dass die Daten von der Mitte zum Ende in umgekehrter Reihenfolge übernommen werden. Letzteres wird einfach aus Gründen der Vereinfachung gemacht, da nun das neu enstehende Datenfeld mit Hilfe zweier Datenzeiger i und j von aussen zur Mitte hin abgearbeitet werden kann. Überschneiden sich die beiden Zeiger beim Mischen, ist dies ein sicheres Zeichen, dass der Mischvorgang beendet ist.

Die obere Abbildung zeigt das Mischen der Datenmengen mit Hilfe des dynamischen Hilfsarrays, dass bei jedem Aufruf der Funktion merge neu angelegt wird. Das Array, das der Funktion übergeben wird, besteht immer aus zwei Blöcken, hier sind es die Folgen 2,3 und 5,7. Sortiert wurden die Teilfolgen schon in vorherigen Schritten. Bedingt durch das Umsortieren in das Hilfsarray stehen die kleinsten Daten immer ganz aussen. Somit ist es eine Kleinigkeit die Daten an den Zeigern i und j zu vergleichen, in das ursprüngliche Feld zu kopieren, und die Zeiger zur Mitte zu bewegen. Es wird immer der Zeiger um eine Position verschoben, dessen Wert der kleinere und der zu kopierende ist.

Jetzt fehlt nur noch die Funktion mergesort, die für das Teilen zuständig ist. Aufgerufen wird unter Angabe des Feldes, des kleinsten lo und des höchsten Indexes hi. Ist die Bedingung lo < hi erfüllt, also mehr als ein Element übergeben, wird die Funktion erneut rekursiv aufgerufen. Erst wenn die Bedingung nicht mehr stimmt, kommt es zum Mischen der letzten beiden Datenmengen.
Da mergesort gleich zwei Aufrufe hintereinander hat, ist der Algorithmus nicht ganz so überschaubar. Man muss sich jetzt vorstellen, dass der erste Aufruf solange ausgeführt wird, bis nur noch ein einziges Element übergeben wird, die Abfrage ist negativ und die Rekursion führt einen Rücksprung aus. Nun kann der zweite Aufruf erfolgen, der zu Folge haben kann, dass wiederum der erste Aufruf erfolgt. Erst wenn die Bedingung im zweiten Aufruf unwahr ist, stehen sich zwei gleich grosse Datenmengen gegenüber, die von der Funktion merge gemischt und damit in die richtige Reihenfolge gebracht werden.

NATURAL MERGE SORT

Basierend auf dem Merge Sort macht es sich zu Nutze, dass die vorhandenen Daten schon auf eine natürliche Weise vorsortiert sind. Eine zufällig vorhandene sortierte Folge wird als Lauf oder englisch Run bezeichnet. Unten ist ein unsortiertes Array mit zehn Datensätzen abgebildet. Es hat jetzt schon die Eigenschaft, mehrere durch Zufall vorsortierte Teilmengen zu beinhalten. Die senkrechten Striche trennen die einzelnen Läufe, hier sind es fünf, voneinander, dienen aber lediglich der Visualisierung. Im einfachsten Fall besitzt ein Run nur ein einziges Element, nämlich dann, wenn der direkte Nachfolger kleiner ist. Diese Runs sind nicht künstlich erzeugt worden. Sie kommen gerade in grösseren Datenmengen recht häufig vor.

Im normalen Merge Sort wird so vorgegangen, dass das erste Mischen nur mit zwei Elementen erfolgt, im zweiten schon mit vier, usw. Mit dieser Variante des Mischens wird immer ein vorderer mit einem hinteren Lauf gemischt. Der wesentliche Unterschied ist der, dass die Anzahl der zu mischenden Elemente nicht von der Basis 2 abhängt und somit ein schnellerer Ablauf möglich ist. Leider ist die Umsetzung programmiertechnisch nicht sehr einfach, obwohl der Algorithmus seine Rekursion einbüsst. Da die Grösse der einzelnen Läufe nicht konstant ist und diese während des Abschreiten des Arrays indirekt ermittelt wird, ist der iterative Weg sicherlich der einfachere.

Um den Algorithmus etwas konkreter zu erklären, sei vorweg noch gesagt, dass das Array immer als Ganzes und alle Runs hintereinander bearbeitet werden. Nimmt man die Abbildung, sieht man, dass der erste Lauf mit dem letzten gemischt im Hilfsarray an den ersten drei Positionen abgelegt wird. Im nächsten Schritt werden die 1, 6, 7, 0, 4 und 9, nachdem sie gemischt wurden, in umgekehrter Reihenfolge an die letzten sechs Plätze im Hilfsarray geschrieben. Von der Funktionsweise her unterscheidet sich dieses Verfahren kaum vom Merge Sort.
Die beiden Laufzeiger i und j werden wie gewohnt, so lange von aussen aufeinander zu verschoben, treffen sie sich, sind alle Runs bis auf den mittleren bearbeitet. Nun folgt ein neuer Durchlauf. Diese undefinierte Länge der einzelnen Läufe hat zur Folge, dass sich die beiden Zeiger nur sehr selten genau in der Mitte treffen. In der oberen Grafik im zweiten Durchlauf begegnen sie sich an der vierten Position, der 3. Es kommt auch vor, dass sich die Zeiger an einem Element überschneiden, das noch zu einem Run gehört. Dennoch wird abgebrochen und das einzelne Element als neuer Run interpretiert.
Man verspricht sich von Natural Merge Sort einen Geschwindigkeitsgewinn, da auf die natürlich vorkommende Sortierung zurückgegriffen werden kann. Testläufe mit dem beiliegenden Programm stringSort können dies leider nicht bestätigen. Es sollte auch wohl überlegt sein, ob die vorliegende Variante wirklich eingesetzt werden sollte, da das Sortierverhalten instabil ist. Es wäre zwar kein grosses Problem, die Stabilität zu implementieren, doch würde dies auf Kosten der ohnehin schon schlechten Performance gehen.

Download

Programm zum Vergleich der Algorithmen