W dniu 2012-10-14 12:06, kenobi pisze:


> w pierwszym przejsciu liczysz histogram, czyli
> 256 offsetow, w drugim wstawiasz wzgledem tych
> ofsetow i masz zgrubnie posortowane, reszte
> podobnie lub ew merge sortem bedzie potezny
> speedup ;)


Całą idea i "prawdziwy speedup" wynika stąd,
że surtujemy _w odwrotnej kolejności_ algorytmem
stabilnym. najpierw posortujemy po niższym
bajcie. Ok. Teraz sortujemy po wyższym.
Jeśli jakieś dwie liczby mają taki sam bajt wyższy,
to nie zostanie zamieniona ich kolejność.
A, że był wcześniej posortowane po niższym,
to są posortowane po obydwu słownikowo.
koniec.

żadnych dodatkowych kontenerów, żadnych histogramów,
żadnego mergesorta nie wiadomo skąd.
Tylko dodatkowa tablica (stabilne sortowanie przez
zliczanie nie działą w miejscu) i wydajność;)

pzdr
bartekltg