Por ejemplo, si la lista original es [6, 7, -1, 0, 5, 2, 3, 8] deberemos ordenar recursivamente [6, 7, -1, 0] y [5, 2, 3, 8] con lo cual obtendremos [-1, 0, 6, 7] y [2, 3, 5, 8]. Si intercalamos ordenadamente las dos listas ordenadas obtenemos la solución buscada: [-1, 0, 2, 3, 5, 6, 7, 8].
Codigo Merge-Sort
package javaapplication1;
// fichero Mergesort.java
import java.util.Date;
public class JavaApplication1 {
public static void main(String [] arg) {
int n = 10000;
// generar n números aleatoriamente
int [] v = new int[n];
for (int i=1; i<n; i++) {
v[i] = (int) (Math.random()*100);
}
System.out.println("Vector antes de ordenar:");
for (int i=1; i<n; i++) {
System.out.println("v["+i+"] = "+v[i]);
}
// ordenar los números
Date antes = new Date();
mergesort(v, n);
Date despues = new Date();
long etime = despues.getTime()-antes.getTime();
System.out.println("\nTiempo utilizado por mergesort(): " +
etime + " milisegundos.");
System.out.println("\nVector despues de ordenar:");
for (int i=0; i<n; i++) {
System.out.println("v["+i+"] = "+v[i]);
}
System.out.println("Ya he terminado.");
} // fin de main()
// mezclar ordenadamente dos ficheros ordenados
// na, nb número de elementos de los conjuntos a y b
// ia, ib, ic posición donde empiezan los conjuntos en
// los vectores a[], b[] y c[]
static void merge(int a[], int ia, int b[], int ib,
int c[], int ic, int na, int nb)
{
int i=ia, j=ib, k=ic;
// copiar ordenadamente a y b sobre c
while (i<na+ia && j<nb+ib) {
if (a[i] < b[j]) {
c[k++] = a[i++];
}
else {
c[k++] = b[j++];
}
}
while (i<na+ia) {
c[k++] = a[i++];
}
while (j<nb+ib) {
c[k++] = b[j++];
}
} // fin de merge()
public static void mergesort(int vect[], int n)
{
// se supone que n debe ser potencia de 2
int [] aux = new int[n];
// valores de k: 1, 2, 4, 8, ...
for (int k=1; k<n; k*=2) {
// valores de j = 0, 2, 4, 6, 8, ... (k=1)
// j = 0, 4, 8,12,16, ... (k=2)
//for (j = 0; j<n-k; j+=2*k) // para n potencia de 2
for (int j = 0; j<=n-k; j+=2*k) {
merge( vect, j, vect, j+k, aux, j,
Math.min(k,n-j), Math.min(k,n-j-k) );
}
System.arraycopy(aux, 0, vect, 0, n);
}
aux = null;
} // fin de mergesort()
} // fin de la clase Mergesort
Animacion de Merge Sort
