Análisis de Algoritmos

también conocido como Merge-Sort:
 Básicamente trata sobre el ordenamiento por mezcla funciona de la siguiente manera:
–      Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
–      Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
–      Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
–      Mezclar las dos sublistas en una sola lista ordenada.
El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:
–      Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.

–      Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

En pocas palabras se le puede denominar como un método de ordenamiento capaz de desmantelar un vector en varias partes y organizarlos de menor a mayor. Su ventaja es que es efectiva al momento de ejecutar sus procesos. Y su mas grande desventaja es el tiempo de la duración de la misma.

Pseudocodigo

SubProceso mezclar (arreglo1, n1, arreglo2, n2, arreglo3 por referencia)

                x1<-1;

                x2<-1;

                x3<-1;

                Mientras (x1 <= n1 y x2 <= n2) Hacer

                               Si arreglo1[x1] < arreglo2[x2] Entonces

                                               arreglo3[x3] <- arreglo1[x1];

                                               x1<-x1 + 1;

                               Sino

                                               arreglo3[x3] <- arreglo2[x2];

                                               x2<-x2 + 1;

                               FinSi

                              

                               x3<-x3 + 1;

                FinMientras

                Mientras x1 <= n1 Hacer

                               arreglo3[x3] <- arreglo1[x1]

                               x1<-x1 + 1;

                               x3<-x3 + 1;

                FinMientras

                Mientras x2 <= n2 Hacer

                               arreglo3[x3] <- arreglo1[x2]

                               x2<-x2 + 1;

                               x3<-x3 + 1;

                FinMientras

FinSubProceso

SubProceso mezcla ( array por referencia, n )

                n1 <- 0; n2 <- 0; x <- 1; t <- 1;

                Si n > 1 Entonces

                               Si n mod 2 = 0 Entonces

                                               n1 <- trunc(n / 2);

                                               n2 <- n1;

                               Sino

                                               n1 <- trunc(n / 2);

                                               n2 <- n1+1;

                               FinSi

                               dimension vector1[n1];

                               dimension vector2[n2];

                               Para x<-1 Hasta n1 Con Paso 1 Hacer

                                               vector1[x] <- array[x];

                               FinPara

                               Para t <- 1 Hasta n2 Con Paso 1 Hacer

                                               vector2[t] <- array[x];

                                               x <- x+1;

                               FinPara

                               mezcla(vector1,n1);

                               mezcla(vector2,n2);

                               mezclar(vector1, n1, vector2, n2, array);

                FinSi

FinSubProceso

Proceso principal

                Escribir "Ingrese el tamano del vector";

                Leer num;

                dimension vector[num];

                Para i<-1 Hasta num Con Paso 1 Hacer

                               Escribir "Ingrese el numero ", i;

                               Leer vector[i];

                FinPara

                mezcla(vector, num);

                Escribir "los elementos ordenados del vector son: ";

                Para i<-1 Hasta num Con Paso 1 Hacer

                               Escribir vector[i];

                FinPara

FinProceso

por medio de este video veremos el funcionamiento de el merge-sort