a) Descripcion
Este metodo de llama mezcla porque combina dos o mas secuencias en una sola secuencia ordenada por medio de la seleccion repetida de los componenetes accesibles en ese momento.
Un arreglo individual puede usarse en lugar de dos secuencias si se considera como de doble extremo. En este caso se tomaran elementos de los dos extremos del arreglo para hacer la mezcla. El destino de los elementos combinados se cambia despues de que cada par ha sido ordenado para llenar uniformemente las dos secuencias que son el destino. Despues de cada pasada los dos extremos del arreglo intercambian de papel, la fuente se convierte en el nuevo destino y viceversa.
b) Algoritmo
1.- Inicio
2.- Dividir la secuencia A en dos mitades denomindas 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.
IMPLEMENTACION EN JAVA
public class MergeSort {
public static void main(String[] args) {
int [] vectorM ={9, 75, 14, 68, 29, 17, 31, 25, 4, 5, 13, 18, 72, 46, 61, 3,2,15,34,23,25,0};
System.out.println("Vector aun no ordenado: ");
for (int i = 0; i < vectorM.length; i++) {
System.out.printf(" "+vectorM[i]);
}
System.out.println("");
System.out.println("MergeSort");
setVetor(vectorM);
merge(0,vectorM.length-1);
System.out.println("Vector ya ordenado: ");
for (int i = 0; i < vectorM.length; i++) {
System.out.printf(" "+vectorM[i]);
}
}
/* Vetor de entrada */
private static int[] vector;
public static int[] getVetor() {
return vector;
}
public static void setVetor(int[] vector) {
MergeSort.vector = vector;
}
/*
* Método recursivo que divide el vector en dos y luego se funde y clasifica
*/
private static void merge(int inicio, int fin) {
if (inicio < fin) {
int medio = (inicio + fin) / 2;
merge(inicio, medio);
merge(medio + 1, fin);
mesclar(inicio, medio, fin);
}
}
// Ordena y pidió dos piezas de vectores adyacentes y les ordena conjuntamente
private static void mesclar(int inicio, int medio, int fin) {
int tamaño = fin - inicio + 1;
/*
* A partir de un vector temporal para ayudar en la clasificación
vector es una copia temporal del extracto será ordenado
*/
int[] temporal = new int[tamaño];
// temporal=vector;
System.arraycopy(vector, inicio, temporal, 0, tamaño);
/*
* Atar para ordenar vector, utilizando el vector temporal, utilizando
índices i y j para cada pieza del vector de fusión
*/
int i = 0;
int j = medio - inicio + 1;
//Dependiendo de las condiciones, toma un elemento de una sección o de otro
for (int posicion = 0; posicion < tamaño; posicion++) {
if (j <= tamaño - 1) {
if (i <= medio - inicio) {
if (temporal[i] < temporal[j]) {
vector[inicio + posicion] = temporal[i++];
} else {
vector[inicio + posicion] = temporal[j++];
}
} else {
vector[inicio + posicion] = temporal[j++];
}
} else {
vector[inicio + posicion] = temporal[i++];
}
}
}
}