У меня есть некоторые данные, поступающие от оборудования. Данные поступают в блоки по 32 байта, и потенциально есть миллионы блоков. Блоки данных разбиты на две половины следующим образом (буква - один блок):

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

или если пронумерованы

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

Сначала все блоки с четными индексами, затем нечетные блоки. Существует ли специальный алгоритм для правильного переупорядочения данных (в алфавитном порядке)?

Ограничения в основном на пространстве. Я не хочу выделять другой буфер для переупорядочения: просто еще один блок. Но я также хотел бы сохранить количество ходов на низком уровне: простая быстрая сортировка была бы O (NlogN). Есть ли более быстрое решение в O (N) для этого особого случая переупорядочения?