Mam dane pochodzące ze sprzętu. Dane są dostarczane w blokach po 32 bajty i potencjalnie są miliony bloków. Bloki danych są rozproszone na dwie połowy w następujący sposób (litera to jeden blok):

<code>A C E G I K M O B D F H J L N P
</code>

lub jeśli są ponumerowane

<code>0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
</code>

Najpierw wszystkie bloki z parzystymi indeksami, potem dziwne bloki. Czy istnieje wyspecjalizowany algorytm do poprawnej zmiany kolejności danych (kolejność alfabetyczna)?

Ograniczenia dotyczą głównie przestrzeni. Nie chcę przydzielać innego bufora do ponownego uporządkowania: tylko jeszcze jeden blok. Ale chciałbym też zachować niską liczbę ruchów: prosty quicksort to O (NlogN). Czy istnieje szybsze rozwiązanie w O (N) dla tego specjalnego przypadku zmiany kolejności?