MergeSort

MergeSort

Merge sort. Algoritmo basado en la técnica de diseño de algoritmos Divide y Vencerás.

Definición

Consiste en dividir el problema a resolver en subproblemas del mismo tipo que a su vez se dividirán, mientras no sean suficientemente pequeños o triviales.

Pasos

1. Ordenar una secuencia S de elementos:
   1. Si S tiene uno o ningún elemento, está ordenada
   2. Si S tiene al menos dos elementos se divide en dos secuencias S1 y S2, S1 conteniendo los primeros n/2, y S2 los restantes.
   3. Ordenar S1 y S2, aplicando recursivamente este procedimiento.
   4. Mezclar S1 y S2 ordenadamente en S
2. Mezclar dos secuencias ordenadas S1 y S2 en S:
   1. Se tienen referencias al principio de cada una de las secuencias a mezclar (S1 y S2).
   2. Mientras en alguna secuencia queden elementos, se inserta en la secuencia resultante (S) el menor de los elementos referenciados y se avanza esa referencia una posición.

Seudocódigo

MergeSort (T [ ] a,  entero n) 
{ 
 si ( n>1) entonces 
 { 
  a1= a[0...n/2 -1] ; // Primera mitad 
  a2= a[n/2...n-1] ; // Segunda mitad 
  MergeSort(a1, n/2);
  MergeSort(a2, n – n/2); 
  Merge(a1,a2,a, n); 
 }
} 

Merge(T [ ] a1,T [ ] a2, T [ ] a, entero n)
{ 
 entero i, j, k; 
 i = j = k =0; 
 mientras(i < n/2 && j < n - n/2)
 { 
  si(a1[i] < a2[j]) entonces
  { 
  b[k] = a1 [i]; 
  i++; k++;
  }  
  sino
  { 
  b[k] = a2[j]; 
  j++; k++;
  } 
 }
 mientras(i < n/2)
 { 
  b[k] = a1 [i]; 
  i++; k++;
 }  
 mientras(j < n-n/2)
 { 
  b[k] = a2 [j]; 
  j++; k++;
 }  
}  

Complejidad del algoritmo

Para ordenar un arreglo de tamaño n se ordenan 2 arreglos de tamaño n/2, de aquí el 2T(n/2), y luego se consume O(n) en realizar la mezcla. Resolviendo la ecuación recurrente tenemos que T(n) = O(n log n)

Propiedades

• Es Estable.
• Memoria Auxiliar O(n).
• No ordena en el lugar.
• Es O(n log n).

Mezclas Sucesivas (MergeSort)

Fue desarrollado en 1945 por John Von Neumann. Se aplica la técnica divide y vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada. Si n = 1 solo hay un elemento por ordenar, sino se hace una ordenación de mezcla de la primera mitad del arreglo con la segunda mitad. Las dos mitades se ordenan de igual forma.

MergeSort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. MergeSort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar MergeSort de manera que sólo requiera O(1) espacio extra, y el mal rendimiento de las listas enlazadas ante el acceso aleatorio hace que otros algoritmos como quicksort den un bajo rendimiento, y para otros como heapsort sea algo imposible. El algoritmo de MergeSort es un algortimo de sort que presenta algunas propiedades interesantes. En primer lugar, el orden del algorimo es en el caso (n log n), y esto ocurre tanto en el peor caso, como en el mejor caso, como medio ya que el tiempo que insume el algoritmo no depende de la disposición inicial de los elementos del vector. En segundo lugar es un algoritmo que requiere de un espacio extra de almacenanimiento para poder funcionar.

Fuente

• Curso de programación II, Universidad de Ciencias Informáticas.
• PEÑA M., Ricardo. Diseño de programas. Formalismo y abstracción. Prentice-Hall, 1998.
• WEISS, M. A., Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana, 1995.
• WIRTH, Niklaus. Algoritmos y Estructuras de Datos. Pentice Hall, 1987.