Tengo algunos datos que vienen del hardware. Los datos vienen en bloques de 32 bytes, y hay potencialmente millones de bloques. Los bloques de datos se dispersan en dos mitades de la siguiente manera (una letra es un bloque):

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

o si esta numerado

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

Primero todos los bloques con índices pares, luego los bloques impares. ¿Existe un algoritmo especializado para reordenar los datos correctamente (orden alfabético)?

Las restricciones son principalmente en el espacio. No quiero asignar otro búfer para reordenar: solo un bloque más. Pero también me gustaría mantener el número de movimientos bajo: un simple orden rápido sería O (NlogN). ¿Hay una solución más rápida en O (N) para este caso especial de reordenación?