Der schlimmste Sortieralgorithmus
Nicht nur das Entwickeln möglichst leistungsfähiger, vor allem schneller Sortieralgorithmen ist anspruchsvoll. Es ist nämlich durchaus auch eine intellektuelle Herausforderung, einen Sortieralgorithmus möglichst zu verlangsamen, ohne das Sortierziel aus den Augen zu verlieren. Sinnlos wäre hingegen, den Sortieralgorithmus ständig irgendetwas für den Sortierfortschritt und das Sortierergebnis unnötiges zwischenzeitlich rechnen zu lassen, künstliche Pausen einzulegen oder einfach nur zu warten, ob etwas von allein passiert (was natürlich nimmer der Fall ist). Nein, es muß tatsächlich eine Änderung des Ordnugnsniveaus erfolgen, und der Algorithmus muß zumindest das Potential, die Chance haben, irgendwann mit einer sortierten Menge zu enden.
Die meisten Sortieralgorithmen beruhen ausschließlich oder vorwiegend auf dem Befehlspaar „Vergleichen und und optionales Tauschen (wenn die Reihenfolge der verglichenen Elemente der gewünschten Ordnung zuwiderläuft) jeweils zweier Elemente“. Doch es gibt auch Sortieralgorithmen, die diese Befehlsreihenfolge umkehren und mithin der Erreichung des Sortierzieles scheinbar maximal entgegenwirken. In Wirklichkeit wird der bisherige Sortierfortschritt nur nicht fixiert, nicht darauf aufgebaut. Dabei werden erst zwei beliebige Elemente vertauscht und erst dann die gesamte Menge auf Ordnung bzw. Sortiertheit geprüft (oder, wenn man zuerst prüft, dann kann man so wenigstens schon sortierte Mengen von überflüssiger „Sortierung“ befreien). Die Wahl der zu tauschenden Elemente erfolgt entweder zufällig (Bozosort) oder durch systematische Permutationsenumeration (Bogosort). Diese Sortieralgorithmen, die auch schon erreichte Teilordnungen immer wieder sehr wahrscheinlich zerstören, sind vermutlich die ineffizientesten überhaupt (bis jemand noch langsamere findet), aber auch sie können die Sortierung nach Zeitaltern, die jegliche astronomische / kosmologische Zeiträume schnell und weit überschreiten, nicht für alle Ewigkeit verhindern. Während beim Bogosort nach spätestens n! Vertauschungen und Prüfen der Menge auf Sortiertheit Schluß sein muß (n: Anzahl der Sortierelemente), weil alle Permutationen der Sortierelemente geprüft wurden, kann es beim Bozosort noch wesentlich länger dauern.