Iterativ versus rekursiv
Die Grundstruktur jedes Sortieralgorithmus' besteht entweder aus Schleifen (iterativ) oder im Sich-Selbst-Aufrufen bestimmter Unterprogramme oder gar der eigentlichen Sortierroutine (rekursiv). Oft können diese Strukturen adäquat ineinander transformiert werden, sie sind dann äquivalent, was sich auch in (zumindest nahezu) gleicher Sortiergeschwindigkeit zeigt. Ein sehr einfaches und entsprechend bekanntes Beispiel liefert die Berechnung der Fakultät.
Während die meisten iterativen (nicht nur Sortier-)Algorithmen wohl recht simpel in ihre rekursiven Pendants umgewandelt werden können, ist der umgekehrte Weg meistens deutlich schwieriger. Oft ist es nur (?) möglich, indem eine für die Rekursion wichtige Speicherstruktur (der sog. Stack) nachgebildet („emuliert“) und anstatt des echten Stacks, der bei der Rekursion zum Zuge kommt, entsprechend verwendet wird. Allerdings ist auch diese Umwandlung grundsätzlich als gelungen anzusehen, weil die Hauptstruktur dann eine Schleife ist. Salopp könnte man solche Algorithmen als pseudorekursiv-stackiterativ (oder nur eines von beiden) bezeichnen. Vollendet ist diese Umwandlung erst, wenn auch dieser (Pseudo-)Stack entbehrlich wird. Beispiele dafür sind im Programm das Dekompositionsmerge und diverse Quicksorts. Bei zwei (pseudo-)iterativen Sortieralgorithmen, nämlich den beiden Naturalmergesorts, die wie einfaches Mergesort aussehen und eben einen (Pseudo-)Stack benötigen, ist dem Programmautor eine Umwandlung in die rekursiven Pendants bisher nicht gelungen und wohl auch nichttrivial.
Um die simultanen / parallelen / Multithreadingalgorithmen hinsichtlich der Anzahl zu sortierender Elemente möglichst uneingeschränkt nutzen zu können, war es nötig, den während der Programmlaufzeit leider konstanten sog. Stackspeicher des Programmes (und damit aller seiner Threads) soweit wie möglich zu reduzieren. Dieser wird jedoch für die Rekursionen benötigt, sodaß das Programm dann ggf. wegen (Stack-)Speichermangels abbricht. Infolgedessen wandelte ich die allermeisten Rekursionen in Iterationen um. Die Grundideen dazu (nötige Stack-Ersatzsspeicherstruktur, Methodik der Umwandlung) entnahm ich Robert Sedgewicks Buch „Algorithmen“. Diese Transformation hat keinen signifikanten Einfluß auf die Laufzeit und überhaupt keinen auf die Animation der Algorithmen.
Die Rekursion bei Sortieralgorithmen wird gern und bevorzugt zur Realisierung des sog. Verteile-und-herrsche-Prinzips („divide et impera“) verwendet.