Zitat von
glkgereon:
soweit ich weiss ist 0(n*log(n)) doch besser als 0(n)...oder?
Äh. Nein. log(n)>1 für n>e. Ergo ist n*log(n)>n für alle n>e (2.7 sonstwas)
Zitat von
glkgereon:
einen Linear-sortierenden Algo kann ich dir auch schreiben
Äh. Her damit und Du bekommst einen Nobelpreis. Und wirst Weltpräsident. Und erhälst das halbe Königreich. Und die Prinzessin oben drauf.
Ich glaub, Du verwechselst da was. Es gibt natürlich Sortierverfahren, die linear sortieren, aber dazu musst Du Einschränkungen in Kauf nehmen. Du must spezielle Kentnisse über den Schlüssel verwenden (Zahl zwischen 1 und X oder so).
Es ist schon bewiesen, das allgemeine Sortierverfahren im Optimum einen Aufwand von O(n log n) haben. Besser geht es einfach nicht. Jedenfalls nicht in diesem Universum.