Zitat von
glkgereon:
mein Algo kann Ganze Zahlen in linearer Zeit sortieren.
Klappt nicht.
Delphi-Quellcode:
Type
TIntegerArray = Array Of Integer;
Var
A : TIntegerArray;
Begin
SetLength (A,2);
A[0] := 0; A[1] :=maxint;
Sort (A); // <- peng
End;
Zitat von
glkgereon:
Mit anderen Typen als ganzen Zahlen... Theoretisch ist es möglich.
Praktisch wohl kaum.
Du machst, wie ich bereits sagte, starke Einschränkungen bezüglich des Schlüssels. Die Schlüssel sind abhängig vom vorhandenen Speicher, was nun wirklich nicht praktikabel ist. Die Laufzeit ist abhängig von der Verteilung der Schlüssel sowie von den Schlüsseln selbst.
Wenn Du schon (annähernd) linear sortieren willst, dann wenigstens mit einem praktikablen Verfahren, als dem hier. Z.B. Bucketsort. Das geht aber auch nur mit Schlüsseln, die einigermaßen gleichmäßig verteilt sind.
Im Übrigen ist Quicksort bei Arrays bis 2,5Mio Elementen immer noch wesentlich schneller.