On 14.10.2012 00:51, PK wrote:
> Sortowanie optymalne: max 62 porównania.
To rozwiązanie jest optymalne tylko jeżeli chodzi o liczbę porównań[*].
A nie np. czas, czy pamięć na rzeczywistym systemie(czy nawet na
abstrakcyjnej maszynie).

Możemy rozważyć mergesort na 10 procesorach - wykona trochę więcej
porównań niż Twoje "optimum", ale za to zakończy pracę prawie 2 razy
szybciej ;)

[*] Na typach bez znaku możemy sortować po kolejnych bitach. Nie
wykonujemy w takim przypadku porównań między liczbami a szukamy
pierwszej liczby z zapalonym n-tym bitem po lewej i niezapalonym po
prawej, zamieniamy, powtarzamy aż do spotkania indeksów. Powtarzamy
rekurencyjnie dla obu kawałków i n-1 bitu. Mamy 0 porównań - to dopiero
optimum ;)

--
Pozdrawiam
Michoo