Mein Beitrag

Mein Beitrag zu diesem Programm besteht aus folgenden Punkten:

• Wandermerge, ein recht langsamer, dafür aber wenigstens bedingt stabiler und  In-Situ -Verschmelzungsalgorithmus (implementiert beim Merge- und beim Naturalmergesort). Ich nannte ihn so, weil der sog. „Workspace“ sichtbar durch das Array wandert.
• n-Quicksort mit dem Kernalgorithmus n-Partition (Verallgemeinerung der Lomuto-Partitionierung), der ein (Teil-)Array mit einer (fast) beliebigen Anzahl an Pivotelementen partitioniert.
• Einige wenige Verschmelzungsalgorithmen in diesem Programm funktionieren nur mit gleichgroßen (d.h., gleiche Elementeanzahlen) Teilarrays. Diese sind nur bei Mergesort mit Elementeanzahlen gleich einer Zweierpotenz gewährleistet. Damit diese Verschmelzungsalgorithmen für beliebig bzw. verschieden große Teilarrays und mithin auch für normales und Naturalmergesort nutzbar werden, entwickelte ich ein zunächst rekursives Unterprogramm zwecks Verschmelzungen („equalmerge“), das diese anspruchsvollen Verschmelzungsalgorithmen von verschiedengroßen Teilarrays abschirmt und diese mit nur gleichgroßen Teilarrays aufruft. Später transformierte ich dessen Rekursion noch in eine Iteration, wie ich es überall im Programm tat, um den Stackspeicher zu schonen. Die Funktionalität dieses Unterprogrammes kann ich nicht beweisen, aber bislang führte es seine Funktion fehlerlos aus.
• Die rekursive Variante des Permutationsenumerationsalgorithmus von Steinhaus, Johnson und Trotter (implementiert in zwei Bogosorts).
• Weiterhin stammt der Blocktauschalgorithmus „Kreuzindex“ in allen drei Geschwindigkeitsstufen von mir. Er funktioniert so, daß jedes Sortierelement vor dem Tausch seine Zielposition angeheftet bekommt. Der Rest ist mehr oder minder effizientes In-Situ-Umordnen.
• Zuguterletzt stammen das einfache iterative Quicksort, die Naturalmergesorts, die wie einfaches Mergesort aussehen, sowie einige weitere Vereinfachungen und Modifikationen einiger Sortier- und Verschmelzungsalgorithmen von mir.