Ich habe einige Daten von der Hardware. Daten kommen in Blöcken von 32 Bytes und es gibt möglicherweise Millionen von Blöcken. Datenblöcke werden auf folgende Weise in zwei Hälften gestreut (ein Buchstabe ist ein Block):

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

oder wenn nummeriert

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

Zuerst alle Blöcke mit geraden Indizes, dann die ungeraden Blöcke. Gibt es einen speziellen Algorithmus, um die Daten korrekt neu zu ordnen (alphabetische Reihenfolge)?

Die Einschränkungen liegen hauptsächlich im Weltraum. Ich möchte keinen weiteren Puffer für die Neuordnung zuweisen: nur einen weiteren Block. Aber ich möchte auch die Anzahl der Züge niedrig halten: Eine einfache Quicksortierung wäre O (NlogN). Gibt es in O (N) eine schnellere Lösung für diesen speziellen Umordnungsfall?