README

MergeSortDemo

Программа представляет собой инструмент для сортировки больших файлов строк – от 2 кб и более (сотни мегабайт). При этом размер оперативной памяти используемой для сортировки составляет всего 1 мб, однако, при этом, требуется 2 * рамер_исходного_файла места на диске. Имеется ограничение на максимальную длину строки - 500 символов, а при сравнении учитываются только первые 50 символов.

Проект создан на Delphi 2009.

Использует метод двухпутевого сбалансированного слияния. Начальное разбиение исходных данных на два файла производится так: строки считываются в память порциями (размер которых определяется объёмом доступной приложению памяти (константа - 1 мб)), к каждой порции применяется алгоритм внутренней сортировки Quicksort, и затем отсортированные порции (образующие серии) поочередно записываются в два файла. Далее производится многократное естественное слияние: получаемые в каждой итерации серии, также записываются в два файла, которые становятся исходными для следующей итерации. Процесс продолжается до получения единственной серии в одном файле. Параллелизм реализован за счёт разбиения исходного файла на 4 части и применения к каждой из них вышеописанной процедуры в отдельном потоке. В итоге получаем 4 отсортированных файла. Далее производится попарное их слияние в двух потоках. Результат – два файла, которые объединяются завершающим слиянием в результирующий файл (к сожалению, лишь в одном потоке). Вообще говоря, существует способ распараллеливания и отдельно взятого слияния, однако применение его к массивам с нефиксированной длиной элемента сопряжено с рядом сложностей.

Программа создаёт в процессе работы временные файлы в подкаталоге Temp каталога файла-результата, и поэтому требует наличия свободного места на соответствующем диске в объёме равном удвоенному размеру исходного файла. При работе с относительно большими файлами (от 500 Мб) при использовании hdd, работа программы начинает замедляться из-за длительных позиционирований головок. В этом случае выигрыш от распараллеливания сортировки сходит на нет (и даже в минус). Помогает делу, использование разных физических дисков для исходного и результирующего файлов, либо использование накопителей с быстрым временем доступа (я тестировал на ram-диске, вероятно на ssd также должны быть хорошие результаты).