Постановка задачи:
имеется до (порядка) 4 миллиардов МД5 (16-ти байтных) хэшей, записанных в бинарном файле. Нужно их отсортировать по возрастанию и записать в тот же файл. Это нужно для создания бесконечно масштабируемой базы данных "отпечатков" файлов, способной определять, "знает" ли программа новфй очередной файл, или же он попадается впервые. Надеяться на то, что это поместится полностью в оперативке для внутренней сортировки, не приходится. 

Изучил все темы на этом форуме, прочитал соответствующие главы классических трудов Кнута "искусство программирования", где вопросам внешней сотировки уделяется довольно много внимания. Учитывая специфику задачи: равномерное распределение 256 битных целых, полагаю, наиболее эффективным будет алгоритм н-путевого слияния?  Существует ли более эффективный алгоритм?

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

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

вот такие мысли появляются, хочется услышать советы.

Это сообщение отредактировал(а) Alexk553 - 4.5.2010, 12:24

Ладно, буду использовать алгоритм такого типа:

определить доступный размер ОЗУ;
выбрать 2^N куска для разбиения, чтобы они поместились в память;
отсортировать стандартным алгоритмом каждый кусок;
записать эти куски в новый файл, на месте недостающих элементов оставить нули;
выбрать все первые (минимальные элементы) насколько позволяет память (занести в буфер);
построить дерево турнира;
из него выбрать победителя;
там, где был победитель поставить следующее число из соответствующей серии(отсортированного куска);
повторить турнир только там,где есть новые элементы.;
повторять до тех пор, пока один из кусков (серия не станет нулевой длины).
заполнить все куски новыми данными с диска.
Повторять, пока данные не закончатся.

недостаток тот, что требуются элементы с формальной бесконечностью. 

На мой взгляд вполне неплохой алгоритм, но вот рассматриваю , как альтернативу ему корзинную сортировку, тт.е. 
создаём те же два в энной степени конвейера и начинаем линейно просматривать гигантский файл. Старшие биты извлекаемых хэшей задают номер корзины. По заполнению одного из этих буферов производится сброс всех накопленных данных в файлы(!). Продолжаем до тех пор, пока не джочитаем до конца наш гигантский файл. К каждому файлу применяем внутреннюю сортировку.

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

К сожалению, в данных алгоритмах совершенно не используется равномерность распределения величин сортируемых элементов. 

У меня где-то был алгоритм сортировки в файле, реализованый на Паскале.
Поможет?

Ну, смотря какой метод исполоьзуется. В принципе, мне нужна не реализация, а оценка качества. Я тут посмотрел на досуге все существующие алгоритмы, пришёл к такому алгоритму:

0) по длине файла(или в БД это прописано явно) вычисляется количество хэшей. На основании этой информации и наличия ОЗУ дпринимается ршение о количестве корзин для сортировки. Она выражается степенью двойки. 
Если количество корзин превышает заданное, например, 1024, то переходим к 1), иначе 2)
1) 1-й проход - файл читается линейно блоками. счётчики по количеству корзин накапливают информацию о том, сколько нужно места в каждой корзине. Затем выделяется новый временный файл в количестве одна штука  и в нём делается разметка ля смещений хэщей и сопунтствующих записей.  2-й проход - файл читается блоками линейно, после анализа каждого блока накопленные хэши для каждого кармана перемещаются группами для оптимизации дисковой системы. после обработки всех данных содержимое каждого кармана считывается в оперативную память и делается внутрення сортировка (та же корзинная, но внутренняя, никаких рекурсий либо сортировка подсчётом). затем данные скидываются во времнный файл. Всё, масв отсортирован.
2) суть та же, что и в 1) методе, но первый проход не делается, а сразу открываются все файлы на записить, и к ним добавляются записи. внутренняя сортировка, затем простое склеивание файлов и массив отсортирован.

Этот метод имеет линейную (!!!) скорость выполнения на известной структуре данных, что важно для огромных массивов. А также очень простой и понятный алгоритм, в отличие, от, например, пирамидальной сортировки 

Главный вопрос темы решён. Этот метод позволяет работать с порядка десять в 18-й степени файлами, если принять 4 Гб ОЗУ. Порядка. может на один больше-меньше.

Теперь чисто теоретический вопрос из любопытства, а как быть, если число хэшей в таблице десять в 23 степени, к примеру. Короче,если корень кубический из числа элементов порядка количества элементов, которые могут разместиться в ОЗУ.

Это кусок из методички по организации баз данных. Надеюсь, тебя не смутит украинский.

Спасибо за пример.  Однако, этот алгоритм крайне неэффективный. Каждый вызов poisk сопровождается линейным чтением!
вызов на 65 и 66 строчке этого дела в цикле! Страшно представить работу этого алгоритма даже на 1000000 записей.

Тогда храни хэши в наборе файлов (скажем по 100 мб каждый файл) так чтобы один этот файл можно было загрузить в оперативку для обработки
И создай что-то типа словаря файлов в котором храни 
-имя файла
-первый хэш
-последний хэш

а во время сортировки используя этот файл словарей можно определять в который из файлов хэшей записать.
Что-то типа принцыпа работы индексов в СУБД

Эм... Alexk553, ты поставил практическую или теоретическую задачу? Если теоретическую - то давайте писать код, а если практическую - то я бы сделал все на стандартных технологиях: загоняем файл в СУБД, считываем по возрастанию и записываем, все ж быстрее получится, особенно если грамотно прописать работу с базой.