Wie logisch richtig sortieren: 1,2,3,21 (nicht 1,2,21,3)?

[Der_Unwissende]

Hi,
dachte eigentlich topologisches Sortieren besagt nur, dass nicht alle Elemente Paarweise vergleichbar sind. Also nimmt man "zufällig" ein Element und sortiert alle Elemente, die sich mit diesem Vergleichen lassen. Nun schaut man sich die Menge der unbetrachteten Elemente an und geht wieder so vor, zum Schluß erhält man also eine Sortierung, dass für jede Teilmenge von paarweise vergleichbaren Elementen sortiert ist, doch die Reihenfolge dieser Teilmengen wäre dann beliebig.
Aber klar, kenne ich auch am ehesten im Zusammenhang mit Graphen und kann es auch noch falsch in Erinnerung haben (begegnet mir eher selten als Begriff).

Was Merge- und Quicksort angeht, so sollte man wirklich nicht vergessen, dass die Asymptotische Laufzeit konstante Faktoren versteckt (sonst stellt sich schnell die Frage warum Quicksort und nicht Bubblesort, beide O(n^{2})), aber umsonst heißt der Quicksort nicht Quicksort. Amortisiert komme ich ja auch nur auf O(n*log n), aber was wichtiger ist, wie alzmair schon sagte, ich muss immer die ganze Menge im Speicher halten.

Also welche Sortierung die schnellste ist (immerhin auch in linearer Zeit möglich), hängt doch stark von der Menge der Daten und der Art des Speichers ab, sollte hier aber nicht das Problem sein.