История изменений

Если можно создать новый файл, я бы сначала посчитал индексы и сохранил бы старшие 4 бита в память, получатся сожрёт полгига, а потом уже на основании полученной карты собирал бы последовательно исходные элементы, соответстивующие текущему блоку, вычислял бы их индекс, помещал бы в гигабайтный буфер в память, а потом уже блок из буфера писал.

Если нужно менять порядок на месте, разделил бы весь массив на блоки, для каждого блока завёл бы текущий индекс, дальше последовательно искал бы в каждом блоке первый элемент, этому блоку не принадлежащий, после чего устраивал бы обмены этих элементов. По завершении этого шага у меня были бы блоки, в которых только те элементы, которые должны находиться в этих блоках. Дальше уже тривиально, переставить элементы внутри одного гигабайтного блока несложно. Минус - потенциально двойная перезапись файла, но при этом и чтения и записи последовательно внутри каждого блока.

Если можно создать новый файл, я бы сначала посчитал индексы и сохранил бы старшие 4 бита в память, получатся сожрёт полгига, а потом уже на основании полученной карты брал бы последовательно исходные элементы, вычислял бы их индекс, помещал бы в гигабайтный буфер в память, а потом уже буфер писал.

Если нужно менять порядок на месте, разделил бы весь массив на блоки, для каждого блока завёл бы текущий индекс, дальше последовательно искал бы в каждом блоке первый элемент, этому блоку не принадлежащий, после чего устраивал бы обмены этих элементов. По завершении этого шага у меня были бы блоки, в которых только те элементы, которые должны находиться в этих блоках. Дальше уже тривиально, переставить элементы внутри одного гигабайтного блока несложно. Минус - потенциально двойная перезапись файла, но при этом и чтения и записи последовательно внутри каждого блока.