AlgoTests

Решение тестового задания, когда-то полученого мной от Яндекса.

Задание

Пусть у нас на диске есть файл размером 4 гигабайта. Его можно представить, как 2^30 32-битных беззнаковых чисел. Нужно отсортировать этот файл. То есть программа должна сгенерировать еще один файл размером в 4 гигабайта, в котором содержатся те же числа, что и в исходном, но упорядочены по возрастанию. Стандартные алгоритмы сортировки (qsort, std::sort) напрямую применить невозможно, так как для их выполнения нужно как минимум 4 гигабайта оперативной памяти. Но отсортировать числа на диске возможно, если использовать дополнительное пространство на жестком диске. Нужно написать консольную программу, которая в argv[1] получает имя файла, который нужно отсортировать (размер файла до 16Gb, размер кратен четырем), в argv[2] - имя файла, в который нужно записать отсортированные данные.

Ограничения:

1. Программа не может рассчитывать, что возможно выделить более 256Mb памяти.
2. Программа должна эффективно использовать несколько ядер.

Кратко опишу, как будет оцениваться результат. Нам бы хотелось получить решение, по которому можно было бы оценить качество кода (простота чтения, скорость работы). Засчитывается решение, которое:

1. Компилируется ;)

2. Правильно завершается, даже при неправильных данных, недостаточных ресурсах, а не просто падает в случайных местах.

3. Корректно сортирует произвольный файл.

4. Код можно прочитать и понять.

5. Работает эффективно. Эффективно значит

   1. используя немного памяти, зато полностью загружая CPU.
   2. нельзя придумать существенно более эффективное (на десятки процентов, или с принципиально лучшей временной сложностью) решение. Экономию в 2-3% путем микрооптимизаций не учитываем.

Было бы идеально, если бы решение представляло собой один cpp файл, который компилировался бы gcc 4.x или ms visual studio c++ compiler'ом версии 7.1. Если не получится собрать, будем разбираться. Желательно бы в решении не использовать copy/paste из библиотек.