Cómo ordenar datos de 4GB con memoria de 1GB

1. ¿Necesita mirar todos los datos para hacer el ordenamiento? Por ejemplo, si está buscando 4 GB de registros de la base de datos y desea ordenar por nombre, solo necesita los datos del nombre y un puntero al registro del que provienen. Eso puede ser considerablemente más pequeño. Una vez que haya hecho ese tipo, puede escribirlo como un índice (que le permite mantener efectivamente los datos ordenados en múltiples órdenes), o puede usarlo para escribir un nuevo archivo, con los datos ordenados.
2. Puedes ordenar en trozos. Divide tus datos en 8 fragmentos de 1/2 GB cada uno y clasifica cada uno de ellos. Con cada uno de los que ya están ordenados, puede hacer una inserción en el disco en un nuevo archivo de manera razonablemente rápida (su sistema operativo debería ayudar almacenando las lecturas del disco, lo que será eficiente ya que ahora está leyendo cada archivo en orden) .
3. La mayoría de los sistemas de archivos modernos admiten archivos dispersos. Si su objetivo es simplemente poder acceder a cada registro rápidamente, en lugar de ponerlos en un orden particular, puede crear una función hash basada en la clave que desea usar, luego escribir cada registro en un archivo con un desplazamiento basado en ese hash. Ahora puede buscar inmediatamente el registro adecuado siempre que se le dé la clave.

Depende del tipo de datos que esté ordenando.

Si el archivo contiene palabras, puede seguir el enfoque de la ordenación externa.

Simplemente divide el archivo en fragmentos de datos, clasifica cada fragmento en RAM y combina los resultados.

Fundamentalmente clasificando los fragmentos y luego fusionando los resultados parciales mientras escribe los datos resultantes en el almacenamiento secundario.

Tenga en cuenta que al leer, por ejemplo, cadenas en una matriz, como preparación para la ordenación, la matriz ocupará considerablemente más espacio que las cadenas puras, por lo que necesita más fragmentos que 4.

1. Por paginación … todo el conjunto de datos no tiene que estar en la memoria de una vez. Los sistemas operativos modernos ya resumen RAM y disco en memoria virtual. Moverá las páginas de memoria del disco a la memoria principal y viceversa. La clasificación tardará unas pocas magnitudes más que si se cargara completamente en la memoria.
2. Use un tipo eficiente de memoria como el tipo burbuja. Solo requiere acceso a los objetos N y N + 1 a la vez.

De muchas maneras. Toma esto de la biblioteca y pasa un tiempo con él:

The Art of Computer Programming: Volume 3: Sorting and Searching (2nd Edition): Donald E. Knuth: 9780201896855: Amazon.com: Books