Ordenamiento por Intercalación Merge

Códigos del Métodos de Ordenamiento por Intercalación:

Intercalación Merge:

                               Descripción

Cuando se dispone de dos vectores ya ordenados y se desea obtener un tercer vector también ordenado, se puede realizar la ordenación con un método denominado Mezcla (Merge en inglés).

Supongamos que A es un vector ordenado de m elementos y B es otro vector ordenado de elementos. La operación de mezcla producirá un nuevo vector de m + n elementos. El método más sencillo, pero menos eficaz, consiste en colocar una lista detrás de la otra y luego ordenarla.

Sin embargo este método no aprovecha la propiedad de que los vectores A y B ya están ordenados, por ello debe recurrir normalmente al sistema de mezcla el cual cosiste en comparar los dos primeros elementos de los vectores (A y B) y enviar al menor al tercer vector, continuando con el elemento comparado pero no enviado con el siguiente elemento del vector que contiene al elemento menor comparado anteriormente y así sucesivamente.

Una vez que se terminaron los elementos de un vector, se procede a vaciar los elementos restantes del otro vector.

Algoritmo

1.- Inicio
2.- Dividir la secuencia A en dos mitades denominadas B y C.
3.- Mezclar B y C combinando cada elemento en pares ordenados.
4.- Llamar A a la secuencia mezclada y repetir los pasos 1 y 2, esta vez combinando los pares en cuadriples ordenados.
5.- Repetir los pasos anteriores duplicando cada vez la longitud de las secuencias combinadas hasta que quede ordenada la secuencia original.
6.- Fin del Algoritmo.

Código

import java.io.*;
public class MezclaNaturalMain {
    public static void main(String [] args)throws Exception{
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String nombreArchivo = null;
        MezclaNatural mezcla1 = new MezclaNatural();
        //Solicita el nombre de un archivo para poder ordenarlo
        System.out.println("Nombre del archivo:");
        nombreArchivo = br.readLine();
        //Despliega el contenido del archivo sin ordenar
        mezcla1.desplegar(nombreArchivo);
        //Ordena el contenido del archivo
        mezcla1.ordenar(nombreArchivo);
        //Verifica que el archivo este ordenado correctamente
        mezcla1.verificarOrdenamiento(nombreArchivo);
    }
}