Ordenar archivos más grandes con RAM más pequeña

Supongamos que tenemos que ordenar un archivo de 1 GB de enteros aleatorios y el tamaño de RAM disponible es de 200 Mb, ¿cómo se hará?

La forma más fácil de hacer esto es usar la clasificación externa .
Dividimos nuestro archivo fuente en archivos temporales de tamaño igual al tamaño de la RAM y primero ordenamos estos archivos.
Supongamos que 1 GB = 1024 MB, por lo que seguimos los siguientes pasos.

1. Divida el archivo de origen en 5 archivos temporales pequeños, cada uno de 200 MB (es decir, igual al tamaño de la RAM).
2. Ordene estos archivos temporales uno a uno usando el RAM individualmente (cualquier algoritmo de clasificación: clasificación rápida, clasificación por combinación).

Ahora tenemos pequeños archivos temporales ordenados como se muestra en la imagen de abajo.

Figura: división del archivo de origen en archivos temporales ordenados más pequeños

Ahora hemos ordenado los archivos temporales .

1. Los punteros se inicializan en cada archivo.
2. Se crea un nuevo archivo de 1 GB de tamaño (tamaño del archivo de origen).
3. El primer elemento se compara de cada archivo con el puntero.
4. El elemento más pequeño se copia en el nuevo archivo de 1 GB y el puntero se incrementa en el archivo que apuntaba a este elemento más pequeño.
5. Se sigue el mismo proceso hasta que todos los punteros han atravesado sus respectivos archivos.
6. Cuando todos los punteros han pasado, tenemos un nuevo archivo que tiene 1 GB de enteros ordenados.

Así es como se puede ordenar cualquier archivo más grande cuando existe una limitación en el tamaño de la memoria principal (RAM) .

La idea básica es dividir el archivo más grande en archivos temporales más pequeños, ordenar los archivos temporales y luego crear un nuevo archivo usando estos archivos temporales. Esta pregunta se hizo en la entrevista de Infosys para el perfil de programador de potencia.