Сортировка в одном файле

Алгоритм упорядочения данных в одном файле (то есть на месте) получается естественным обобщением метода пузырька. Роль такого пузырька играет порция данных, в которой постепенно накапливаются записи с наибольшими (или наименьшими) значениями ключа. Величина порции составляет половину выделенного для сортировки объема оперативной памяти. Допустим, что файл разбивается на N порций (зон).

В начале процесса в память считываются две первые порции (зоны) данных и упорядочиваются там как единый массив, после чего половина массива с меньшими значениями ключа (назовем ее "нижней") записывается во вторую зону. На освободившееся место считывается третья зона, содержимое памяти вновь сортируется каким либо методом внутренней сортировки, и нижняя половина записывается в третью зону. Процесс повторяется для всех зон до N-1 включительно. После считывания N-й зоны и внутренней сортировки уже верхняя половина (пузырек) записывается в N-ю зону. Таким образом ключи последней зоны уже заняли свое окончательное положение в файле. Процесс повторяется для оставшихся N-1 зоны , затем для оставшихся N-2 зоны и т.д.

Ниже приведен текст функции, реализующей алгоритм.

int BubbleExternSort(char *FileName, int RecLen,

int (*cmp)(const void *r1, const void *r2), int MemSize){

// Внешняя сортировка пузырьком

// FileName - имя бинарного файла, содержащего таблицу

// RecLen - длина записи

// cmp - функция, сравнивающая ключи записей

// возвращает -1,0,1

// MemSize - размер оперативной памяти, который разрешено

// использовать для сортировки

// при нормальном завершении возвращает 0

// в противном случае - код ошибки