Ordenamiento externo: Mezcla Natural (Natural Merge Sort)

1. Algoritmo original.
2. Algoritmo genérico.
3. Ordenando cadenas binarias.
4. Ordenando cadenas.
5. Ordenando enteros grandes.
6. Ordenando objetos.

Entre los métodos de ordenamiento externos más comunes se encuentran el de Mezcla Directa (o Merge Sort) y el de Mezcla Natural (o Natural Merge Sort). El método de Mezcla Natural consiste en aprovechar la existencia de secuencias ya ordenadas dentro de los datos de los archivos. A partir de las secuencias ordenadas existentes en el archivo, se obtienen particiones que se almacenan en dos archivos o ficheros auxiliares. Las particiones almacenadas en estos archivos auxiliares se fusionan posteriormente para crear secuencias ordenadas cuya longitud se incrementa arbitrariamente hasta conseguir la total ordenación de los datos contenidos en el archivo original.

Para ilustrar la Mezcla Natural es muy conveniente utilizar números enteros como los datos almacenados en un archivo, de tal manera que este método funciona como se ilustra en el siguiente ejemplo (se utilizan corchetes o paréntesis cuadrados para separar las secuencias en las particiones):

Nombre del archivo original: Origen
Archivos auxiliares: Auxiliar1 y Auxiliar2

Origen: [10,17],[5,8,9],[3,22,50],[4],[2,20,30],[11,16,19],[6,21,23]

Primera Iteración: Las secuencias que se encuentren dentro del archivo origen se almacenan de forma alternada en los archivos auxiliares:
Partición
Auxiliar1: [10,17],[3,22,50],[2,20,30],[6,21,23]
Auxiliar2: [5,8,9],[4,11,16,19]

Aquí vale la pena resaltar lo que sucede con la secuencia [4] del archivo origen: cuando se realizan las particiones (aún sin entrar al proceso de fusión) los elementos 11, 16 y 19 se convierten en una sola secuencia junto con el 4.

La fusión se realiza por pares de secuencias de manera ordenada, así, la primer nueva secuencia está formada por los elementos de la primera secuencia en el archivo Auxiliar 1 y los elementos de la primera secuencia en el archivo Auxiliar2. Si uno de los archivos auxiliares llega a su fin, las secuencias que se encuentren en el otro archivo sin terminar se vacían directamente después de las nuevas secuencias:
Fusión en el archivo original
Origen: [5,8,9,10,17],[3,4,11,16,19,22,50],[2,20,30],[6,21,23]

Segunda Iteración: Se repite el proceso de partición con las nuevas secuencias:
Partición
Auxiliar1: [5,8,9,10,17],[2,20,30]
Auxiliar2: [3,4,11,16,19,22,50],[6,21,23]

Cuando al comparar un par de secuencias en los archivos auxiliares una de ellas llega a su fin, entonces simplemente se vacía el resto de la secuencia que aún contiene elementos en la nueva secuencia. Este caso se observa claramente en el par de secuencias azules: cuando se llega al elemento 17 del archivo Auxiliar1, la nueva secuencia en la fusión simplemente incluye los elementos 19, 22 y 50 del archivo Auxiliar2 al final.
Fusión en el archivo original
Origen: [3,4,5,8,9,10,11,16,17,19,22,50],[2,6,20,21,23,30]

Tercera Iteración: En este punto se cuenta ya con sólo un par de secuencias. La fusión de éstas da como resultado una secuencia que contiene todos los elementos del archivo Origen en orden ascendente.
Partición
Auxiliar 1: [3,4,5,8,9,10,11,16,17,19,22,50]
Auxiliar 2: [2,6,20,21,23,30]

Fusión
Origen:  [2,3,4,5,6,8,9,10,11,16,17,19,20,21,22,23,30,50]

En este último paso, los datos contenidos en el archivo origen se encuentran ordenados de manera ascendente. En la Mezcla Natural se comparan pares de secuencias contenidas en los archivos auxiliares con el objetivo de formar nuevas secuencias durante el proceso de fusión.

En el archivo adjunto se encuentra el código que implementa la Mezcla Natural utilizando nombres de personas como datos de los archivos, por lo que las comparaciones que se llevan a cabo a la hora de realizar las particiones y fusiones utilizan el método "compareTo" propio de la clase String.

NOTA: Este código maneja archivos de tipo binario, para probarlo se puede utilizar el archivo de prueba que se encuentra en el post Archivo para probar algoritmos de Ordenamiento Externo.


MezclaNatural.java