Сортировка больших файлов.

[stpdqstns]

Здравствуйте. Столкнулся со следующей проблемой: нужно отсортировать содержимое файла по возрастанию, размер файла более 4Gb, немного подумав, решил разбить исходный файл на кусочки по 50Mb, по отдельности сортируя их содержимое посредством std::sort, и далее поочередно сливая их std::merge, получается отсортированный файл. Потестил на файле в 650Mb, сортируется около 20-ти минут, процессор 2-х ядерный, загружается на 50%, а одним их основных условий задачи является максимальная загрузка CPU, подскажите, пожалуйста, как можно это осуществить? Советы по улучшению алгоритма также принимаются.

[MihalNik]

Что в файле? (тип данных)

[stpdqstns]

беззнаковые 4-х байтовые числа

[MihalNik]

Эта задача эффективно решается индексированием (упорядочение разложением в массив). Дважды (по младшему и старшему слову (паре байтов)).

[stpdqstns]

Сообщение от MihalNik

Эта задача эффективно решается индексированием (упорядочение разложением в массив). Дважды (по младшему и старшему слову (паре байтов)).

не совсем вас понял

[MihalNik]

Подобные числа в очень большом кол-ве не упорядочивают на основе сравнения
Например, самое наивное, в 4-прохода:
1-ый:
Массив 2^16 - инкрементируется по младшему слову чисел
Последовательным сложением получают смещения чисел.
2-ой:
Числа записываются в новый файл аналогичного размера по вычисленным смещениями (которые также по ходу сдвигают). Делается буферизация, заводится еще массив, например, 2^16 x 1024 числа по 4 байта. И массив 2^16 с позициями в буфере.
При заполнении любого буфера - запись соотв. чисел в файл по соотв. смещению. В конце проход по всему массиву буферов и запись в файл что осталось.

Аналогичная процедура в 2 прохода с записью нового файла но только по старшим словам чисел.

[waleri]

Сообщение от stpdqstns

процессор 2-х ядерный, загружается на 50%, а одним их основных условий задачи является максимальная загрузка CPU, подскажите, пожалуйста, как можно это осуществить?

Запустите два потока, каждый сортирует один из файлов, по окончании берут следующий и т.д. По завершении всех файлов уже один поток сливает файлы.