Ordenamiento 2: mezcla y quicksort

Ordenar un millón de valores comparando todos los pares lleva unos 500 mil millones de comparaciones; el ordenamiento por mezcla necesita unos 20 millones.

Dividir el problema, resolver las mitades

Los métodos de la unidad anterior trabajan con toda la lista a la vez y lo pagan con unas n² comparaciones. Los dos métodos de esta unidad siguen otro plan, llamado divide y vencerás. Se divide la lista en partes más pequeñas, se ordena cada parte con el mismo método y luego se combinan las partes ordenadas. La división sigue hasta que una parte tiene un valor o ninguno, y una lista de un valor ya está ordenada. Como el método se llama a sí mismo con listas más pequeñas, es recursivo (la unidad 6 estudia la recursión en detalle).

Ordenamiento por mezcla: el trabajo está en la mezcla

El ordenamiento por mezcla (merge sort) corta la lista por la mitad, ordena la mitad izquierda, ordena la mitad derecha y mezcla las dos mitades ordenadas en una. Lo ingenioso es la mezcla. Dos listas ordenadas se pueden combinar mirando solo sus valores del frente. Compara los dos del frente, anota el menor y pasa al siguiente. Repite hasta que una lista quede vacía, y luego copia lo que quede de la otra. Mezclar [1, 4, 7] y [2, 3, 8] da 1 (1 contra 2), 2 (4 contra 2), 3 (4 contra 3), 4 (4 contra 8), 7 (7 contra 8), y luego se copia el 8: 5 comparaciones para 6 valores. Una mezcla de dos listas con n valores en total nunca necesita más de n − 1 comparaciones.

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (right[j] < left[i]) out.push(right[j++]);
    else out.push(left[i++]);
  }
  return out.concat(left.slice(i), right.slice(j));
}

function mergeSort(a) {
  if (a.length <= 1) return a;          // ya está ordenada
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

¿Por qué es rápido? Imagina la división por mitades como niveles. Una lista de 8 valores se divide en 2 listas de 4, luego en 4 listas de 2 y luego en 8 listas de 1: tres niveles, porque 8 se puede partir por la mitad 3 veces. En cada nivel, todas las mezclas juntas tocan cada valor una vez, así que un nivel cuesta como mucho unas n comparaciones. Con log₂ n niveles, el total es de unas n log₂ n. Para un millón de valores son unos 20 millones de comparaciones, contra unos 500 mil millones de los métodos de par en par. Dividida como [38, 27, 43, 3] y [9, 82, 10], como en el laboratorio, la lista [38, 27, 43, 3, 9, 82, 10] lleva 14 comparaciones; el código de arriba la divide en 3 y 4 y lleva 13.

El precio es la memoria. La mezcla necesita un lugar donde escribir el resultado, así que el ordenamiento por mezcla usa una segunda lista tan grande como la entrada. Además, el ordenamiento por mezcla es estable: los valores que se comparan como iguales conservan su orden original, porque la mezcla toma de la lista izquierda cuando los del frente son iguales. Eso importa cuando ordenas una tabla por una columna y luego por otra, por ejemplo por ciudad y luego por nombre.

Quicksort: dividir alrededor de un pivote

El quicksort divide la lista de otra manera. Elige un valor, el pivote, y reacomoda la lista para que todo lo menor que el pivote quede antes que él y todo lo demás después. Este paso se llama partición. Ahora el pivote está en su lugar final, y los dos lados se pueden ordenar por separado con el mismo método. Después no hace falta mezclar nada, porque cada valor de la izquierda ya es menor que cada valor de la derecha.

El laboratorio usa una versión común de los libros de texto que toma como pivote el último valor de cada parte. Con [5, 1, 4, 2, 8], el pivote 8 se compara con los otros cuatro valores, todos menores, así que el 8 se queda al final. La parte siguiente, [5, 1, 4, 2], usa el pivote 2: solo el 1 es menor, así que después de dos intercambios la lista es [1, 2, 4, 5, 8]. Una comparación más resuelve [4, 5]. Total: 8 comparaciones y 2 intercambios.

Cuando el pivote cae cerca del medio, cada división parte el problema por la mitad y el quicksort lleva unas n log₂ n comparaciones, como el ordenamiento por mezcla. Además trabaja dentro de la lista original, sin una segunda copia. Pero un mal pivote hace daño. Si la lista ya está ordenada y el pivote es siempre el último valor, cada división separa un solo valor, y el quicksort vuelve a unas n²/2 comparaciones: 10 para [1, 2, 3, 4, 5], igual que el ordenamiento por selección. Las bibliotecas reales lo evitan eligiendo el pivote con más cuidado, por ejemplo al azar o como el del medio de tres valores de muestra.