¿Cuál es la forma más eficiente de clasificar 4 TB en una sola máquina con 4 GB de RAM?

Podemos usar una ordenación de fusión externa para ordenar eficientemente grandes conjuntos de datos cuando tenemos restricciones de memoria.
En este caso particular.

1. Divida el conjunto de datos de 4 TB en fragmentos de 4 GB.
2. Lea cada fragmento de 4 GB en la memoria uno a la vez y ordénelo utilizando un algoritmo de clasificación convencional, como Quicksort. Escriba cada fragmento ordenado nuevamente en el disco.
3. Lea los primeros 200 MB de cada fragmento clasificado de 4 GB en la memoria. Estos serán nuestros amortiguadores de entrada. Totalmente, todos los fragmentos de 200 MB ocuparán 2 GB de memoria.
4. Los 2 GB restantes de memoria serán nuestro búfer de salida.
5. Realizamos una fusión n-way en los fragmentos de 200 MB y almacenamos el resultado en nuestro búfer de salida.
6. Cuando nuestro buffer de salida se llena, lo escribimos en el disco.
7. Cuando un búfer de entrada de 200 MB se vacía, leemos los siguientes 200 MB de la parte restante del fragmento original de 4 GB.
8. Cuando hemos agotado todos nuestros fragmentos de 4 GB y todos los búferes de entrada de 200 MB, escribimos el búfer de salida de 2 GB por última vez en el disco y ahora deberíamos tener un conjunto de datos de 4 TB ordenados.

src: clasificación externa

Creo que debería leer mi respuesta a la siguiente pregunta: ¿Cuál sería un algoritmo eficiente para ordenar millones de líneas de cadenas / enteros en un archivo?

En cualquier caso, como parte de esa respuesta, si solo tiene un tipo de datos, creo que el algoritmo más adecuado es el mergesort externo, utilizando la selección de reemplazo de dos vías como el algoritmo de clasificación de ejecución. Esto ha demostrado ser el más eficiente en términos de crear las ejecuciones más grandes, sin importar las características de los datos, lo que reduce el ventilador para el tipo de fusión.