Es ist vollbracht.
mein Algo kann Ganze Zahlen in linearer Zeit sortieren.
Delphi-Quellcode:
procedure Sort(
var A: TIntegerArray);
var Max,Min: Integer;
H: TIntegerArray;
i, j, k:Integer;
begin
Max:=A[0];
Min:=A[0];
for i:=0
to Length(A)-1
do
begin
if Max<A[i]
then Max:=A[i];
if Min>A[i]
then Min:=A[i];
end;
SetLength(H,Max-Min+1);
for i:=0
to Length(H)-1
do H[i]:=0;
for i:=0
to Length(A)-1
do Inc(H[A[i]-Min]);
k:=0;
for i:=0
to Length(H)-1
do
for j:=1
to H[i]
do
begin
A[k]:=i+Min;
Inc(k);
end;
end;
Mit anderen Typen als ganzen Zahlen...
Theoretisch ist es möglich.
Praktisch ein ziemlicher aufwand^^
im Nachhinein habe ich rausgefunden das dieser Algo im Prinzip dem CountingSort entspricht.
Quicksort ist tatsächlich der schnellste
vergleichsbasierte algo.