Как оптимизировать алгоритм сортировки файла?
===============================================

 Всем доброго времени суток!  

Выполнял недавно тестовое задание, в котором требовалось выполнить сортировку файла, размером 4 Гб, используя всего 512 Мб оперативной памяти. Язык — Java, время выполнения задания (НЕ время работы алгоритма) — 4 часа. В файле строки из трех столбцов, второй столбец — дата и время в формате ISO, по нему нужно сортировать.  

Я сделал следующим образом: начинаем считывать из файла строки в ArrayList, пока не забьем память примерно на 250 Мб, после чего массив сортируем алгоритмом Merge Sort (выбрал его, т.к. у него хорошее время выполнения и уже имел с ним дело), и отсортированный массив записываем во временный файл. Потом продолжаем считывать строки из исходного файла, сортируя и сохраняя по этому же принципу. После считывания всего исходного файла используем тот же алгоритм слияния для сборки одного выходного файла, сохраняя промежуточные результаты в, опять же, промежуточных отсортированных файлах.  

По результату задания мне сказали, что алгоритм не оптимален. Есть идеи, как оптимизировать его, но только незначительно (например, написать более шуструю операцию сравнения двух подстрок или еще что-то в этом духе). Но никаких глобальных способов оптимизации так и не придумал.  

У кого есть идеи — подскажите пожалуйста.   

Заранее спасибо! 

 Я не специалист по сортировке, но если быстро перебрать исходный (первый) файл и сделать копию только из второго столбца и номера строки — больше данных влезет в память (это второй файл).  

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

 Ну я бы сделал так.  

  

Читать сроку, запоминать ее смещение от начала файла (int32), длину строки (int32), а время перевести в timestamp (int32) = ~12 байт на запись (+ оверхед явовских контейнеров)  

Сортировать все скопом по timestamp в один контейнер.  

  

И бежать по индексу выкусывая из исходного файла сроки по смещению и длине, добавляя их в новый.  

  

В 512 Мб влезет ~44 млн. срок. (без учета оверхеда контейнеров) 

 А какого рода строки в файле? Может, их можно хранить в памяти компактней. Например, дату/время можно точно уместить в один long, см. Date.getTime(). Может, и с остальными столбцами так можно? 

 А чем вас не устроили классические алгоритмы сортировки последовательностей (см. Д. Кнут, т. 3)? Вполне себе классический случай. Ключевые слова «однофазная»/«многофазная» «однопутевая», «двухпутевая», «турнирная» сортировка.  

  

В качестве экзотики можно сделать вариант с комбинированной сортировкой (чтение блоков, частичная сортировка, смешивание, например как [здесь](http://en.wikipedia.org/wiki/External_sorting)). Но работать будет долго.  

Если есть опасение, что одна строка не влезет в ограничение по памяти — стройте индекс и сортируйте его. 

 Я не до конца понял ваше решение, но если тупо взять, пройтись по файлу и отобрать топ(512мб), записать в файл. Далее опять пройтись, отобрав топ(512мб) но уже начиная от нижней границы предыдущего топа. Всего 8 проходов. 

 1. Сортировать данные по индексу и второму столбцу  

2. MergeSort использует в 2 раза больше оперативной памяти, нежели действительно требуется. В оперативной лучше сортировать по QuickSort (сортировка по умолчанию Arrays.sort()), тогда можно сортировать в 2 раза больше данных.  

3. Так как дата представляется целым числом, можно использовать поразрядную сортировку (которая производит несколько сортировок подсчетом). Она еще быстрее. То есть, если дата представляется числом < 10^18, то сортировку можно произвести всего лишь тремя сортировками подсчетом (по разряду 10^6), которые выполняются за линейное время  

4. ArrayList работает долго. Используйте массив  

5. Не понял, как именно вы сливаете файлы. Их надо сливать по аналогии с MergeSort. То есть не последовательно, а также логарифмически 

 ещё нужно рассмотреть ситуацию, когда в файле находятся всего 3 строки, каждая размером по 650МБ. вы не сможете прочитать ни одну строку целиком, и нужно делать так, как говорит rowdyro 

 Не сочтите за пошлость ;-)   

Но я бы перегнал бы файл в sqlite.   

А дальше с этим можно делать всё что угодно.