Merge sort en detalle

Merge sort: divide y vencerás

El merge sort es el ejemplo por excelencia de la estrategia divide y vencerás. Tiene una complejidad de O(n log n), mucho mejor que el O(n²) del bubble sort para entradas grandes, y es estable (mantiene el orden relativo de elementos iguales).

La idea se resume en tres pasos:

1. Dividir: parte el array por la mitad hasta llegar a trozos de tamaño 0 o 1, que ya están ordenados por definición (el caso base).
2. Vencer: ordena cada mitad de forma recursiva.
3. Combinar: fusiona (merge) las dos mitades ya ordenadas en un único array ordenado.

La función merge

El corazón del algoritmo es fusionar dos arrays ya ordenados en uno solo. Usamos dos índices (uno por array) y vamos eligiendo siempre el menor de los dos elementos pendientes:

function merge(izq, der) {
  const resultado = [];
  let i = 0;
  let j = 0;
  while (i < izq.length && j < der.length) {
    if (izq[i] <= der[j]) {
      resultado.push(izq[i]);
      i++;
    } else {
      resultado.push(der[j]);
      j++;
    }
  }
  // Uno de los dos ya se agotó; añadimos lo que quede del otro.
  return resultado.concat(izq.slice(i)).concat(der.slice(j));
}

La función mergeSort

Con merge resuelto, mergeSort solo divide y delega:

function mergeSort(arr) {
  if (arr.length <= 1) return [...arr]; // caso base

  const medio = Math.floor(arr.length / 2);
  const izq = mergeSort(arr.slice(0, medio));
  const der = mergeSort(arr.slice(medio));
  return merge(izq, der);
}

Fíjate en que slice crea copias: el algoritmo no muta el array original. ¿Por qué O(n log n)? Hay log n niveles de división, y en cada nivel se procesan en total n elementos al fusionar.

Ejemplos

Merge sort con traza de las divisiones

function merge(izq, der) {
  const out = [];
  let i = 0, j = 0;
  while (i < izq.length && j < der.length) {
    if (izq[i] <= der[j]) out.push(izq[i++]);
    else out.push(der[j++]);
  }
  return out.concat(izq.slice(i)).concat(der.slice(j));
}
function mergeSort(arr) {
  if (arr.length <= 1) return [...arr];
  const medio = Math.floor(arr.length / 2);
  console.log("Divido:", arr.slice(0, medio), "|", arr.slice(medio));
  return merge(mergeSort(arr.slice(0, medio)), mergeSort(arr.slice(medio)));
}
console.log("Ordenado:", mergeSort([5, 2, 8, 1, 9, 3]));