Eu tenho alguns dados provenientes do hardware. Os dados vêm em blocos de 32 bytes e existem potencialmente milhões de blocos. Blocos de dados são espalhados em duas metades da seguinte maneira (uma letra é um bloco):

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

ou se numerado

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

Primeiro todos os blocos com índices pares, depois os blocos ímpares. Existe um algoritmo especializado para reordenar os dados corretamente (ordem alfabética)?

As restrições são principalmente no espaço. Eu não quero alocar outro buffer para reordenar: apenas mais um bloco. Mas eu também gostaria de manter o número de movimentos baixos: um simples quicksort seria O (NlogN). Existe uma solução mais rápida em O (N) para este caso especial de reordenação?