Ordenamiento por mezcla equilibrada

El algoritmo de Ordenamiento por mezcla equilibrada (o mezcla natural) es un algoritmo de ordenación externa estable basado en la técnica divide y vencerás y es una optimización del método de mezcla directa.

Descripción

La idea básica es realizar particiones tomando secuencias ordenadas de máxima longitud en lugar de secuencias ordenadas de tamaño fijo previamente determinadas. Luego se realiza la fusión de esas secuencias ordenadas, alternativamente sobre dos archivos. Repitiendo este proceso secuencialmente, se logra que el archivo quede completamente ordenado.

Para aplicar este algoritmo, se necesitarán cuatro archivos. El archivo original y tres archivos auxiliares. De estos cuatro archivos, dos serán considerados de entrada y dos de salida, alternativamente en cada paso del algoritmo. El proceso termina cuando en la finalización de un paso, el segundo archivo de salida quede vacío.

Vea en wikilibros el código fuente de una aplicación que muestra este ordenamiento externo: Mezcla Equilibrada