Staram się opracować sposób skutecznego sortowania ogromnego zbioru danych, który nie mieści się w pamięci. Oczywistą odpowiedzią na wysokim poziomie jest sortowanie całej masy porcji, które mieszczą się w pamięci za pomocą standardowego algorytmu, zapisywanie ich na dysku, a następnie scalanie. Łączenie ich jest problemem.

Powiedzmy, że dane dzielą się na kawałki C, więc mam pliki C do scalenia. Jeśli wykonam scalanie w C-sposób w jednym przebiegu, to technicznie mam algorytm O (N ^ 2), chociaż taki, który musi tylko wykonać O (N) zapisuje na dysk. Jeśli iteracyjnie scalę je w pliki C / 2, a następnie pliki C / 4 itd., To mam algorytm O (N log N), ale taki, który musi wykonać O (N log N) zapisuje na dysk, a zatem ma zaolbrzymi stały termin.

Jakie jest typowe rozwiązanie tej zagadki? Czy jest jakiś dobry?