Estoy tratando de averiguar cómo ordenar de manera eficiente un gran conjunto de datos que no cabe en la memoria. La respuesta obvia a un nivel alto es ordenar un montón de trozos que encajan en la memoria usando un algoritmo estándar, escribirlos en el disco y luego combinarlos. Fusionarlas es el problema.

Digamos que los datos se dividen en segmentos C, por lo que tengo archivos C para fusionar. Si hago una combinación de C-way en una pasada, técnicamente tengo un algoritmo O (N ^ 2), aunque uno que solo tiene que realizar escrituras O (N) en el disco. Si los fusiono de forma iterativa en archivos C / 2, luego en archivos C / 4, etc., entonces tengo un algoritmo O (N log N), pero uno que tiene que realizar escrituras O (N log N) en el disco, y por lo tanto tiene unaenorme término constante.

¿Cuál es la solución típica a este enigma? ¿Hay alguna buena?