Conociendo el ordenamiento por mezcla (Merge Sort)

guille2 years ago

comment

local_cafe

algorithms icpc

Merge Sort

El Merge Sort o ordenamiento por mezcla, es un ordenamiento con una complejidad computacional logarítmica $O(nlog{n})$, que permite ordenar un listado de elementos de manera muy rápida. Este algoritmo, es el primero de los algoritmos de complejidad logarítmica que se mostrarán en el sitio.

Una de las características con las que cuenta el Merge Sort, es que es un ordenamiento estable. Los ordenamientos estables, son aquellos que una vez que se ha terminado de ordenar el listado, todos los elementos iguales, quedan en el mismo orden en que originalmente estaban en la lista no ordenada. A continuación se muestra un ejemplo:

3 2 1 1 2 3

1 1 2 2 3 3

Como se pudo comprobar, los elementos en negrita similares a los en cursica, quedaron en la misma posición en que originalmente se encontraban. Esta propiedad es conocida como estabilidad de los algoritmos de ordenamiento y no todos cumplen con ella, por eso la importancia de conocerla y evitar caer en errores no deseados.

Algoritmo

Para entender como funciona el Merge Sort, hay que partir de la base del algoritmo que es la mezcla de conjuntos. Definiremos entonces, las primeras reglas para después llegar al algoritmo final.

Si se cuenta con dos listados ordenados, es posible mezclarlos de manera tal que el resultado de la mezcla es la concatenación ordenada de los 2 listados anteriores.
La mezcla de dos listados tiene una complejidad lineal $O(n+m)$, donde n+m es la suma del tamaño de ambos listados.
Divide y vencerás, es la técnica en la que se basa el Merge Sort para primeramente ordenar los sub-listados más pequeños del listado general y luego mezclar todos estos sub-listados.

¿Cómo mezclar dos listados?

Para mezclar dos listados ordenados solo hace falta dos punteros (uno para cada lista), y luego se van comparando los elementos de cada lista en la posición de los punteros, y el elemento menor o mayor (según el criterio del ordenamiento), es el que se toma para el nuevo listado (el resultante de la concatenación) y el puntero de ese elemento se incrementa. Este proceso se repite hasta que ambos listados se hallan completamente concatenado. A continuación un ejemplo con dos listados ordenados:

Divide y vencerás

La idea detrás del divide y vencerás, es como el mismo nombre lo indica, dividir en sub-problemas que más adelante resuelvan el problema final. En el caso del Merge Sort, el lista será dividido en dos sub-listados, luego estos sub-listados serán nuevamente divididos y así sucesivamente, hasta que llega a un listado de dos elementos que puede ser fácilmente ordenado. Luego de llegar a estos sub-listados pequeños de 1 o 2 elementos, se comienzan a mezclar los sub-listados formando nuevos listados ordenados. Este proceso se repite hasta llegar al listados original que en última instancia, quedará ordenado. A continuación un ejemplo de este proceso:

Todo este proceso, tiene una complejidad $O(nlog_2n)$ dado que la altura del árbol que se forma al dividir en sub-listados el listado original es $log_2n$ donde n es la cantidad de elementos y como en cada nivel de este árbol es necesario iterar sobre todos los elementos para mezclarlos, la complejidad es $O(n * log_2n)$.

Código

Implementación en javascript

function merge(list, start, middle, end) {
  let i = start, j = middle, newList = [];
  while (middle > i || end > j) {
      if (i < middle && j < end) {
          list[i] < list[j] ? newList.push(list[i++]) : newList.push(list[j++]);
      } else {
          i < middle ? newList.push(list[i++]) : newList.push(list[j++]);
      }
  }
  newList.forEach((v,k) => list[start + k] = v);
}
function mergeSort(list, start, end) {
  start = start === undefined ? 0 : start;
  end = end === undefined ? list.length : end;
  if (end - start > 2) {
      mergeSort(list, start, Math.floor((end + start) / 2));
      mergeSort(list, Math.floor((end + start) / 2), end);
      merge(list, start, Math.floor((end + start) / 2), end)
  } else if (end - start === 2 && list[start] > list[end - 1]) {
      const tmp = list[start];
      list[start] = list[end - 1];
      list[end - 1] = tmp;
  }
}
const array = [5, 4, 6, 3, 0, 7, 2, 1, 9, 8];
console.log(array);
mergeSort(array)
console.log(array);