q_q
С последним тезисом полностью согласен. Если подходить к задаче практически, то да. Ну а в свое удовольствие можно и велосипеды поизобретать. Кстати, до сих пор изобретают - процесс совершенствования, наверное, бесконечен.

Все же, мне думается, разговор не перейдет в конструктивное русло, пока ты, как инициатор, или кто другой не предложат для обсуждения конкретные частные подзадачи. А пока получается, что-то типа объявления конкурса с неизвестным итогом. И время убъешь и поймешь, что ты лох - надо было бы все не так (это я про себя). Это все таки форум, здесь люди обсуждают проблемы, а не соревнуются. Или я неправильно понимаю (это уже к "подстрекателю" volodya).

PS: в частности, не понимаю почему для начала не взять размер < 4Gb и использовать все таки dword-ы. Суть ограничения, как я понимаю, в том, что нельзя целиком хранить в памяти ни сам файл, ни индексы. А > 4GB достаточно иметь ввиду, чтобы алгоритм позволял произвести доработку до qword (а нет, так и фиг с ним).

Или я неправильно понимаю (это уже к "подстрекателю" volodya).

Во. Теперь еще и меня виноватым сделали. Вы, сперва, с условиями задачи разберитесь. С формулировками разберитесь, а потом пылить начинайте.

У меня есть предложение выбрать какой либо один байт для обозначения конца строки, в противном случае не ясно что делать с двумя пустыми строками, если одна из них оканчивалась на 0A, а другая на 0D. Как встретив 0A0D в отсортированном файле определить это одна пустая строка или две? Вобщем я склоняюсь к мысли что перед сортировкой стоит преобразовать исходный файл, заменив все tab'ы на пробелы, а в конце строки оставить только один 0A или 0D.
Так же неплохо было бы оговорить сколько можно дополнительно памяти использовать. Можно ли кроме выходного, создать временный файл равный ему по размеру?

volodya
"Во. Теперь еще и меня виноватым сделали"

Чего-то мы запарились. Вот для развлечения funny story:

Летают фанеры над столицами мира. Одна и говорит: "..эх, заняться чем что-ли.." Мол, все летаем, летаем, пора бы и приземлиться, на мир вблизи посмотреть... Идея было понравилась, стали приглядывать место для посадки. Но тут вдруг высший разум с ясного неба: "займитесь, займитесь..." и пальцем у виска крутит, мол "вы че, ку-ку ? пролетите и мокрого места не останется". Да, озадачил. Нет, видать, уж лучше в облаках витать (поэзия, однако). С отцем небесным общаться. Ну а тот и рад, давай им истории всяки про деревья райские сказывать, ну те, что с Кнутом вместе зажали. А то говорит, зачахли деревья без внимания-то, окучивать надо, одни злые орклы над ними вьются. Посмотрел народ на поле непаханное да немерянное - это сколько ж Га здеся буде. Взялися подсчитывать, кто в уме, кто на пальцах - не хватат пальцев то. А отец - хитер, давай стыдить их: "О мир, говорит, не могу поверить, что это ты !". Вот так, и Кнутом, и Пряником. Пробил час, кажися с 26-го на 27-е по новому стилю, и молвил он наказ: сортировать поле размером до 2^63 и баста. И еще пилюли прописал: Signed 64-bit и два параметра, три раза в день. Ну, народ давай те пилюли жевать да выплевывать - глотать-то такую нечисть кому охота. Топчутся вокруг, да около - такая пылища поднялась. А око никогда не дремлет, пылить не разрешает и на какие-то разборки посылает. Ну и правильно. Потому что оно ясное и справедливое, а во всем гнусный микрософт и его шайка виноваты. Разрешили такие поля сеять, вот народ и давай стараться: а что если все это сорняками да пустостроками засадить, во весело будет. Не, если конечно как попало, то это просто мусор, а вот если в определенном порядке, то это сортированный мусор. Генератор гигамусора смастерим, в хозяйстве сгодится - можно его потом нехорошим соседям на винт подбрасывать - все же польза. Эх-ма-а... "О мир, не могу поверить, что это ты !"

PS: улыбайтесь, вас снимает скрытая камера !

Честно говоря, я уже устал прикалываться. Но все-таки предлагаю тем, кто возьмется за реализацию проекта перед сортировкой проверить свободное место на диске. Дерево это вам не массив. Это как минимум две ссылки + ключ. Две ссылки qword это уже 16 байт - а это уже может быть сравнимо со средней длиной строки в самом файле. Если ключи по большей части уникальны (как в задачке cresta), то размер индексного файла может быть сравним с размером исходника + еще отсортированный надо сохранить.

Black_mirror
что делать с двумя пустыми строками, если одна из них оканчивалась на 0A, а другая на 0D ... Как встретив 0A0D в отсортированном файле определить это одна пустая строка или две?
Очень просто. Если первый найденный символ 0Dh, то за ним проверяется наличие 0Ah, за 0Ah ничего не проверяется.

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

Так же неплохо было бы оговорить сколько можно ...
Зачем вносить ограничение?

leo
Сказки придумываешь, что же о своей роли скромно умолчал?

Честно говоря, я уже устал прикалываться.
А как тогда расценивать советы: "... проверить свободное место на диске ... 16 байт - а это уже может быть сравнимо со средней длиной строки ..."?