Ich bin auch für eine mathematische Darstellung. Die ganz am Anfang der Diskussion ist sofort verständlich. Man solte es nur formaler hinschreiben: A: { a1, a2, ..., an } Alphabet S1, S2, S3: { a | a € A } Mengen über A (€ = Element von) ≥(A×A) -> {wahr, falsch}: Prädikat (Wahrheitsfunktion) über A×A +: Konkatenation von Symbolen Not: - Negation |S|: - Mächtigkeit von S Ergebnis: Liste einelementiger Mengen über A, sortiert nach ≥ quicksort (S) begin if |S| < 2 then return S wähle beliebiges Element y aus S S1 = { a | a € A, not ≥(a, y) } S2 = { a | a € A, ≥(a, y) } Return quicksort(S1) + quicksort(S2) end "Wähle beliebiges Elelement y" bedeutet hier "zufällig". Somit ist sichergestellt, daß in unendlicher Zeit der Algorithmus terminiert. Das ist für den Fall |S| = 2 von Bedeutung (Es gilt die lexikale Ordnung): 1. quicksort({a, b}) 2. wähle a 3. S1 = {ε} 4. S2 = {a, b} 5. quicksort({ε}) + {quicksort({a, b}) ... usw. Zufällig in unendlicher Zeit bedeutet, daß in Schritt 2 irgendwann einmal b gewählt wird: 1. quicksort({a, b}) 2. wähle b 3. S1 = {a} 4. S2 = {b} 5. quicksort({a}) + quicksort({b}) ... was zur Termination führt.