RunSort

RunSort ist ein Sortierverfahren, das allen modernen Anforderungen an Sortieralgorithmen genügt, dabei aber einfach zu implementieren ist. RunSort sortiert Läufe, das heißt vorsortierte Teilisten.

Eigenschaften von RunSort

RunSort ist sicher, stabil, ordnungsverträglich und teilweise deutlich schneller als andere bekannte Algorithmen wie Quicksort oder TimSort.

Implementierung von RunSort

Liegen die Daten in Form einfach verketteter Listen vor, so kann RunSort durch folgenden Code (in Java) implementiert werden.

Data restList = null;
static Data runSort(Data first, int exp) {
    if (exp == 0)
        return seperateRun(first);

    first = runSort(first, exp-1);
    if (restList == null)
        return first;

    return merge(first, runSort(restList, exp - 1));
}

Die Prozedur seperateRun(first) liefert den ersten Lauf in der Liste first und setzt restList auf das erste Element der restliche Liste. Die Prozedur merge(r1, r2) mischt die beiden vorsortierten Listen r1 und r2 zu einer sortierten Liste zusammen. Der Parameter exp ist beim Aufruf dieses Algorithmus größer als der Logarithmus von R, der Anzahl der Läufe in der Anfangsliste, zu wählen.

Qualitative und Quantitative Leistung von RunSort

RunSort hat eine garantierte Laufzeitschranke von $Z=N \cdot \log R$, wobei $N$ die Anzahl der Listenelement und $R$ die Anzahl der Läufe in der Anfangsliste ist. $Z$ gibt dabei eine obere Schranke für die Anzahl der Vergleiche, der Prozeduraufrufe und der Kopieroperationen an. Daher ist RunSort sicher (im Gegensatz zum Beispiel zu Quicksort).

RunSort ist stabil, wenn das Mischen stabil vorgenommen wird. RunSort ist ordnungsverträglich, da vorsortierte Listen schneller sortiert werden.
RunSort ist sehr schnell. Laufzeitvergleiche mit anderen gängigen Algorithmen finden sich in , ebenso Implementierungen in Java und C++, sowohl für Listen als auch für Felder.