On 24.11.2012 12:36, bartekltg wrote:
>
> Mając dodatkową pamięć dysku równo pierwotnej tablicy
> (a tak naprawdę 0.5) możemy posortować tablicę
> w 4 przebiegach _sekwencyjnego_ odczytu/zapisu.

slawek się potem "poprawił", że plik jest "dużo" (10x) większy niż ram.

Nie do końca rozumiem to 0.5 nawet przy założeniu dane 4 razy większe od
tablicy - mergesort potrzebuje na każdy merge drugie tyle miejsca.
Wychodzi więc mi minimum 1.5 zakładając, że nie robimy ostatniego
scalania. (Mamy 4 bloki po 1/4 n zajmujące na dysku n i żeby dwa z nich
scalić potrzebujemy dodatkowe 0.5n na wynik.)
>
>
> Kołaczą mi się sztuczki ze statystyką i nie jestem pewien,
> czy nie da się tego zrobić lepiej. Ale ciężko będzie,
> 5 przbiegów po dysku to podejrzewam minimum.
> W koncu nawet log(n) jest większe.

W praktycznym przypadku (a nie maksymalnie złośliwym) spróbowałbym z
drzewem prefiksowym w ramie a jak by się przestało mieścić to dopiero
fallback do sortowania. Daje jeden dodatkowy odczyt sekwencyjny i
złożoność k*log(k) w RAMie gdzie k to liczba różnych wartości.


--
Pozdrawiam
Michoo