Mergesort y quicksort

Mergesort y quicksort son los dos ordenamientos de propósito general que se usan de verdad, y los dos aplican divide y vencerás. La diferencia es dónde ponen el esfuerzo: mergesort divide sin pensar y trabaja al unir; quicksort trabaja al dividir y no tiene nada que unir.

Mergesort: partir, ordenar y fusionar

Mergesort parte el arreglo al medio, ordena cada mitad recursivamente y fusiona las dos mitades ordenadas recorriéndolas en paralelo y tomando siempre el menor disponible.

La partición siempre es exacta, así que la recursión tiene profundidad $\log n$ y cada nivel fusiona $n$ elementos. El costo es $\Theta(n\log n)$ siempre: mejor, promedio y peor caso. No hay entrada que lo haga tropezar.

La fusión pide memoria, y a cambio es estable

La fusión necesita un arreglo auxiliar: mergesort no es in situ y usa $\Theta(n)$ de memoria extra. Existen versiones in situ, pero son complicadas y más lentas en la práctica.

A cambio es estable, siempre que al empatar se tome el elemento de la mitad izquierda. Ese detalle de una línea es lo que lo hace la elección por defecto cuando el orden de los empates importa, y es el motivo por el que varios lenguajes lo usan para ordenar objetos.

Quicksort: particionar y seguir

Quicksort elige un pivote y reordena el arreglo para que a la izquierda queden los menores y a la derecha los mayores. El pivote queda en su posición definitiva y se recurre sobre cada lado; no hay paso de combinación.

Trabaja in situ, con memoria extra $O(\log n)$ por la pila de recursión, y sus constantes son mejores que las de mergesort porque recorre el arreglo en el lugar. En promedio es $\Theta(n\log n)$ y suele ser el más rápido de todos.

Todo depende del pivote

Todo depende del pivote. Si parte cerca de la mitad, la profundidad es logarítmica. Si parte mal —el menor o el mayor cada vez—, un lado queda vacío, la recursión se vuelve de profundidad $n$ y el costo salta a $\Theta(n^2)$.

Tomar siempre el primer elemento es exactamente el peor caso con un arreglo ya ordenado, que es una entrada frecuente. Por eso se usa la mediana de tres, o un pivote aleatorio, que vuelve el peor caso improbable en vez de dependiente de la entrada.

Los repetidos y la partición en tres bloques

El otro punto delicado son los elementos repetidos. Una partición en dos bloques con muchas claves iguales manda todo a un lado y reproduce el caso cuadrático.

La solución es particionar en tres: menores, iguales y mayores, y recurrir sólo sobre los extremos. Con pocas claves distintas eso baja el costo a casi lineal. La partición también intercambia elementos a distancia, y eso es lo que le quita la estabilidad.

Las bibliotecas no usan ninguno puro

Las bibliotecas no usan ninguno puro. Introsort arranca con quicksort, corta a inserción en tramos chicos y, si la profundidad de recursión pasa un umbral, cambia a heapsort para garantizar $O(n\log n)$ en el peor caso.

Timsort, del lado de mergesort, detecta tramos ya ordenados y los fusiona: sobre datos reales —que casi nunca son aleatorios— termina bastante por debajo del límite teórico, y es estable.

La partición, que es donde está todo

Mergesort es directo: partir, ordenar cada mitad y fusionar.

const merge = (left: number[], right: number[]): number[] => {
  const result: number[] = [];
  let a = 0;
  let b = 0;

  while (a < left.length && b < right.length) {
    // <= y no <: con iguales gana el de la izquierda, y eso es la estabilidad
    if (left[a]! <= right[b]!) result.push(left[a++]!);
    else result.push(right[b++]!);
  }

  return [...result, ...left.slice(a), ...right.slice(b)];
};

Quicksort no tiene paso de combinación, y a cambio todo el peso cae en la partición:

const partition = (values: number[], low: number, high: number): number => {
  const pivot = values[high]!;
  let boundary = low; // todo lo que está antes de boundary es menor que el pivote

  for (let index = low; index < high; index += 1) {
    if (values[index]! >= pivot) continue;
    [values[boundary], values[index]] = [values[index]!, values[boundary]!];
    boundary += 1;
  }

  [values[boundary], values[high]] = [values[high]!, values[boundary]!];
  return boundary; // el pivote quedó en su posición definitiva
};

Esa última línea es la clave de por qué quicksort no necesita combinar: al terminar la partición, el pivote está exactamente donde va a estar en el arreglo ordenado, y no se lo vuelve a tocar nunca.

Cuál de los dos, y por qué las bibliotecas eligen distinto

Cierre

Mergesort garantiza $n\log n$ y estabilidad a cambio de $n$ de memoria extra. Quicksort ordena in situ y suele ser más rápido, a cambio de un peor caso cuadrático que se controla eligiendo bien el pivote y particionando en tres. La elección es entre garantía y constante.