Diese Sortierroutine – damals noch in Assembler – schrieb ich etwa 1992 auf einer meiner Amigas, um eine 30.000 Zeilen lange Wortliste für PageStream dem Alphabet nach zu sortieren. Sie sollte möglichst schnell sein, wenig Speicher verbrauchen und dazu übersichtlich sein. Die mir damals vorhandenen Quellen erleichterten mir die Auswahl aus vorhandenen Verfahren nicht gerade. Somit begab ich mich an eine eigene Entwicklung. Gegenüber BubbleSort, ja sogar InsertionSort ergibt sich ein Geschwindigkeitsfaktor von bis zu 10.000.000, je nach Größe der zu sortierenden Liste.

Inspiriert zu diesem Algorithmus habe ich mich durch die Entwicklungen an einem schnellen, aber günstigen AD‐Wandler. Flash‐Wandler waren mir damals zu teuer, einfache Rampenwandler waren nicht schnell genug für meine Ansprüche. Mit der sukzessiven Approximation (schrittweisen Annäherung), bei der die Schritte immer kleiner wurden, brauchte man nur sehr wenige Durchläufe, um ein recht genaues Ergebnis zu erzielen. Ein entsprechend gebranntes GAL war schnell hergestellt. Dieses Prinzip übertrug ich in Assembler.

Es werden int(lb(n)+2) Durchläufe pro Eintrag benötigt. n ist die Länge der bereits bestehenden sortierten Liste, zu Beginn also immer 1. Mit fortschreitendem Einsortieren der neuen Werte wird die Liste um einen Eintrag länger. Bei einer Listengröße von 10 Einträgen sind das 5 Durchläufe – damit liegt der Aufwand im Mittel bei dem eines BubbleSort. Bei 100 Einträgen sind es 8 Durchläufe, bei 1000 Einträgen 11. So richtig in Fahrt kommt die Routine bei extremen Listengrößen: 1.000.000 Einträge: 21 Durchläufe (entspricht einem Geschwindigkeitsfaktor von 23.809), 1.000.000.000 Einträge: 31 Durchläufe (16.129.000fach). Leider ist die praktische Verwendbarkeitsgrenze ca. 1.000.000 Einträge, da dann immerhin ca. 18 Minuten lang gerechnet wird!

Der Algorithmus ist freilich etwas komplexer als BubbleSort. Selbst, wenn drei‐ oder viermal so viel Rechenzeit pro Schleifendurchlauf benötigt werden sollte, lohnt sich der Einsatz dieser Routine bereits ab etwa 35 Einträgen. Das Funktionsprinzip ist folgendes: Der aktuelle Wert, den es in die Liste (linksstehend) einzusortieren gilt, wird zuerst mit einem in der Mitte der bereits sortiert vorhandenen Liste verglichen. Je nachdem, ob dieser Vergleichswert zu groß oder klein ist, wird nun ein Viertel des Listenumfangs addiert oder subtrahiert, dann ein Achtel, Sechzehntel usw.. Selbstverständlich muß auch immer aufgerundet werden, da sonst Positionen in der Liste ausgelassen würden. Nach einer gewissen Höchstzahl an Vergleichen ist die richtige Stelle gefunden und der Wert wird in die Liste eingefügt. Insgesamt wird (solange eine gewisse Mindestgröße der Liste gegeben ist) sehr viel weniger Zeit für Vergleiche verpraßt als bei BubbleSort.

Im Falle der etwa 30.000 Zeilen auf einer Amiga mit einem MC68030 (50 MHz) war die Sortierung (unter Verwendung von Assembler) nach sechs Sekunden erledigt; hätte ich BubbleSort benutzt, wären es 2–3 Stunden gewesen. Wie die Tabelle rechts unten zeigt, läßt sich der Rechenzeitaufwand (auf meinem Klapprechner) mit n²÷900.000.000 [s] überschlagen.

In Wikipedia gibt es derzeit (25.7.2009) keinen eigenen Eintrag für dieses Sortierverfahren. Man könnte es mit InsertionSort mit Binärsuche bezeichnen

Um die Ähnlichkeit zweier Zeichenketten zu ermitteln gibt es viele Methoden.

Diese Berechnung ist dann notwendig, wenn beispielsweise der Unterschied zweier unabhängig voneinander editierter Text mit gemeinsamem Ursprung ermittelt werden soll.

Der Levenshtein‐Algorithmus ist sehr einfach zu implementieren, aber nur für kleine Zeichenketten geeignet, da die Laufzeit O(m*n) beträgt. Liegt die Länge beider Zeichenketten noch unterhalb etwa 1 kB, so kann man in vielen Fällen darauf zurückgreifen. Bei dieser Menge ist jedoch der Speicherverbrauch erheblich, denn er folgt ebenfalls m*n.

Für größeres Datenaufkommen müssen andere Wege gefunden werden, etwa der Hirschberg‐Algorithmus, der eine Linearisierung des Levenshtein‐Algorithmus ist. Dieser ist allerdings erheblich aufwendiger zu implementieren.