Ordenamiento externo

Ordenamiento externo es un término genérico para los algoritmos de ordenamiento que pueden manejar grandes cantidades de información. El ordenamiento externo se requiere cuando la información que se tiene que ordenar no cabe en la memoria principal de una computadora (típicamente la RAM) y un tipo de memoria más lenta (típicamente un disco duro) tiene que utilizarse en el proceso.

Un ejemplo de ordenamiento externo es el algoritmo de ordenamiento por mezcla. Supongamos que 900 MB de información deben ser ordenados utilizando únicamente 100 MB de RAM.

1. Léanse 100MB de información en la memoria principal y ordenense utilizando un algoritmo tradicional (típicamente quicksort).
2. Escríbase la información ordenada en el disco.
3. Repítanse los pasos 1 y 2 hasta que toda la información esté ordenada en pedazos de 100 MB. Ahora se deben mezclar todos los pedazos ordenados.
4. Léanse los primeros 10MB de cada pedazo ordenado a la memoria principal (total de 90 MB) y destínense los 10 MB restantes para el buffer de salida.
5. Ordénense los nueve pedazos mezclándolos y grábese el resultado en el buffer de salida. Si el buffer de salida está lleno, escríbase al archivo destino final. Si cualquiera de los 9 buffers leídos queda vacío, se llena con los siguientes 10 MB de su pedazo original de 100 MB o se marca este como completado si ya no hay registros remanentes.

Otro ejemplo es el algoritmo de ordenamiento por mezcla equilibrada, que es una optimización del anterior.

Referencias

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.4: External Sorting, pp.248–379.

Enlaces externos

• Notas de Ordenamiento Externo (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última)..

• Datos: Q209687