Ordenación Externa: Mezcla Equilibrada en C++

Mezcla Equilibrada.

La idea central de este método consiste en realizar las particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias de tamaño fijo previamente determinadas.

Luego realiza la fusión de las secuencias ordenadas, alternativamente sobre dos archivos aplicando estas acciones en forma repetida se lograra que el archivo original quede ordenado.

Para la realización de este proceso de ordenación se necesitarán cuatro archivos. El archivo original F y tres archivos auxiliares a los que se denominaran F1, F2 y F3. De estos archivos, dos serán considerados de entrada y dos de salida; esto, alternativamente, con el objeto de realizar la fusión-partición. El proceso termina cuando en la realización de una fusión-partición el segundo archivo quede vacío.

F: 09 75 14 68 29 17 31 25 04 05 13 18 72 46 61

PARTICIÓN INICIAL F2: 09 75 29 25 46 61 F3: 14 68 17 31 04 05 13 18 72

PRIMERA FUSION-PARTICION F: 09 14 68 75 04 05 13 18 25 46 61 72 F1: 17 29 31

SEGUNDA FUSION-PARTICION F2: 09 14 17 29 31 68 75 F3: 04 05 13 18 25 46 61 72

TERCERA FUSION-PARTICION F: 04 05 09 13 14 17 18 25 29 31 46 61 68 72 75 F1:
10. Si B1=FALSO entonces Escribir R1 en F 11. {Fin del condicional del paso 10} 12. Si B2=FALSO entonces Escribir R2 en F 13. {Fin del condicional del paso 12} 14. Repetir (mientras no sea el fin de archivo de F1) Leer R1 de F1 Escribir R1 en F 15. {Fin del condicional del paso 14} 16. Repetir (mientras no sea el fin de archivo de F2) Leer R2 de F2 Escribir R2 en F 17. {Fin del condicional del paso 16}

Obsérvese que al realizar la tercera fusión-partición el segundo archivo queda vació, por lo que se puede afirmar que el archivo ya se encuentra ordenado.