Я пытаюсь понять, как эффективно сортировать огромный набор данных, который не помещается в памяти. Очевидный ответ на высоком уровне - отсортировать целую кучу фрагментов, которые помещаются в память, используя некоторый стандартный алгоритм, записать их на диск и затем объединить. Слияние их является проблемой.

Допустим, данные делятся на куски C, поэтому у меня есть файлы C для объединения. Если я делаю C-way слияние за один проход, то технически у меня есть алгоритм O (N ^ 2), хотя тот, который должен выполнять только O (N) записи на диск. Если я итеративно объединю их в файлы C / 2, затем в файлы C / 4 и т. Д., То у меня будет алгоритм O (N log N), но тот, который должен выполнять O (N log N) записи на диск, и поэтому имеетогромный постоянный срок.

Какое типичное решение этой головоломки? Есть ли хороший?