MergeSort

MergeSort

Merge sort. Algoritmo de ordenamiento, donde primero ocurre el ordenamiento de los elementos por separado y luego se mezclan.

Ejemplo: Se tiene un arreglo de 8 elementos, se ordenan los 4 elementos de cada arreglo y luego se mezclan. En el arreglo de 4 elementos, se ordenan los 2 elementos de cada arreglo y luego se mezclan. El arreglo de 2 elementos, como cada arreglo sólo tiene n = 1 elemento, solo se mezclan.

Definición

Entrada: Una secuencia de n números <a1 , a2 , …, an>, usualmente en la forma de un arreglo de n elementos.
Salida: Una permutación <a’1 , a’2, …, a’n> de la secuencia de entrada tal que a’1 = a’2 = … = a’n.

Consideraciones

Cada número es normalmente una clave que forma parte de un registro; cada registro contiene además datos satélites que se mueven junto con la clave; si cada registro incluye muchos datos satélites, entonces movemos punteros a los registros y no los registros.

Un método de ordenación se denomina estable si el orden relativo de los elementos no se altera por el proceso de ordenamiento. Importante cuanto se ordena por varias claves.

Hay dos categorías importantes y disjuntas de algoritmos de ordenación:

• Ordenación interna: La cantidad de registros es suficientemente pequeña y el proceso puede llevarse a cabo en memoria.
• Ordenación externa: Hay demasiados registros para permitir ordenación interna; deben almacenarse en disco.

Mezclas Sucesivas (Merge sort)

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.

Merge sort es un ordenamiento estable, paraleliza mejor, y es más eficiente manejando medios secuenciales de acceso lento. Merge sort es a menudo la mejor opción para ordenar una lista enlazada: en esta situación es relativamente fácil implementar merge sort 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.

Implementación

A continuación se muestra el Ordenamiento Merge sort en el lenguaje de programación de alto nivel C++:

  void ordenarMezcla(TipoEle A[], int izq, int der) 
  { 
 if ( izq < der ) 
   { 
  centro = ( izq + der ) % 2;  
       ordenarMezcla( A, izq, centro ); 
       ordenarMezcla( A, centro+1, der); 
       intercalar( A, izq, centro, der );  
   } 
  }
  void intercalar(TipoEle A[], int a, int c, int b ) 
  {
   k = 0; 
      i = a; 
      j = c + 1; 
      n = b - a; 
   while ( i < c + 1 ) && ( j < b + 1 ) 
   {
   if ( A[i] < A[j] ) 
      { 
  B[k] = A[i]; 
          i = i + 1;  
      } 
      else 
      {
 B[k] = A[j]; 
         j = j + 1;  
      } 
      k = k + 1; 
   };
   while ( i < c + 1 ) 
   { 
 B[k] = A[i]; 
      i++; 
      k++; 
   }; 
   while ( j < b + 1 )
  { 
 B[k] = A[j]; 
      j++; 
      k++; 
   }; 
   i = a; 
   for ( k = 0; k < n; i++ ) 
   {
  A[i] = B[k]; 
      i++; 
   }; 
  };

Fuente

• 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.