Data Structure & Algorithms
Merge sort, quick sort y heap sort
Merge sort, quick sort y heap sort comparados por partición, combinación, estabilidad, memoria, peor caso y rendimiento práctico.
- Última actualización
- Actualizada
- Nivel
- Aplicación
Data Structure & Algorithms
Merge sort, quick sort y heap sort comparados por partición, combinación, estabilidad, memoria, peor caso y rendimiento práctico.
Merge sort, quick sort y heap sort ordenan n elementos en O(n log n) bajo condiciones distintas.
O(n log n) y puede ser estable.O(n²).O(n log n) y puede ser in-place, pero no es estable.No existe un ganador universal. Las garantías, memoria, estabilidad, distribución de datos y runtime cambian la elección.
Divide el array hasta obtener segmentos de un elemento y luego combina pares ordenados.
graph TD
A[8, 3, 5, 1] --> B[8, 3]
A --> C[5, 1]
B --> D[8]
B --> E[3]
C --> F[5]
C --> G[1]
D --> H[3, 8]
E --> H
F --> I[1, 5]
G --> I
H --> J[1, 3, 5, 8]
I --> JLa combinación mantiene dos punteros. En cada paso toma el menor valor disponible.
type Comparator<T> = (a: T, b: T) => number;
function merge<T>(
left: T[],
right: T[],
compare: Comparator<T>,
): T[] {
const result: T[] = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (compare(left[leftIndex], right[rightIndex]) <= 0) {
result.push(left[leftIndex]);
leftIndex += 1;
} else {
result.push(right[rightIndex]);
rightIndex += 1;
}
}
while (leftIndex < left.length) {
result.push(left[leftIndex]);
leftIndex += 1;
}
while (rightIndex < right.length) {
result.push(right[rightIndex]);
rightIndex += 1;
}
return result;
}Usar <= y tomar primero desde left conserva la estabilidad cuando las claves son equivalentes.
function mergeSort<T>(values: T[], compare: Comparator<T>): T[] {
if (values.length <= 1) return [...values];
const middle = Math.floor(values.length / 2);
const left = mergeSort(values.slice(0, middle), compare);
const right = mergeSort(values.slice(middle), compare);
return merge(left, right, compare);
}merge produce una secuencia ordenada y conserva todos los elementos.La recurrencia es:
T(n) = 2T(n/2) + O(n)Hay log n niveles y cada nivel combina n elementos:
O(n log n) en mejor, promedio y peor caso;O(n) para arrays de combinación, más O(log n) de call stack;slice() crea copias adicionales. Una implementación optimizada usa índices y un buffer reutilizable.
Elige un pivot y particiona:
menores | pivot | mayoresDespués ordena recursivamente las dos regiones.
El pivot termina en su posición final después de una partición correcta.
function quickSort<T>(values: T[], compare: Comparator<T>): void {
const partition = (low: number, high: number): number => {
const pivot = values[high];
let boundary = low;
for (let index = low; index < high; index += 1) {
if (compare(values[index], pivot) < 0) {
[values[index], values[boundary]] = [values[boundary], values[index]];
boundary += 1;
}
}
[values[boundary], values[high]] = [values[high], values[boundary]];
return boundary;
};
const sortRange = (low: number, high: number): void => {
if (low >= high) return;
const pivotIndex = partition(low, high);
sortRange(low, pivotIndex - 1);
sortRange(pivotIndex + 1, high);
};
sortRange(0, values.length - 1);
}Esta implementación modifica el array.
Durante el loop:
[low .. boundary) < pivot
[boundary .. index) >= pivot
[index .. high) sin procesarAl final, intercambiar el pivot con boundary lo coloca entre ambas regiones.
Si el pivot divide de forma razonable:
T(n) = 2T(n/2) + O(n) = O(n log n)Si siempre queda en un extremo:
T(n) = T(n - 1) + O(n) = O(n²)O(n log n);O(n²);O(log n) promedio, O(n) peor caso;Opciones:
La aleatorización ofrece una garantía probabilística, no elimina matemáticamente el peor caso.
Con muchos valores iguales, una partición binaria puede hacer trabajo innecesario. Three-way partition separa:
< pivot | = pivot | > pivotSolo las regiones estrictamente menores y mayores necesitan recursión. Esta variante es importante en datos con pocas claves distintas.
Para limitar el stack, procesa recursivamente la partición menor y continúa iterativamente con la mayor. Así la profundidad puede mantenerse en O(log n) incluso si las particiones son desiguales, aunque el tiempo de un mal pivot siga siendo O(n²).
Construye un max-heap y mueve repetidamente el máximo al final.
function heapSort(values: number[]): void {
const siftDown = (start: number, end: number): void => {
let root = start;
while (true) {
const left = root * 2 + 1;
if (left > end) return;
let largest = left;
const right = left + 1;
if (right <= end && values[right] > values[left]) {
largest = right;
}
if (values[root] >= values[largest]) return;
[values[root], values[largest]] = [values[largest], values[root]];
root = largest;
}
};
for (let index = Math.floor(values.length / 2) - 1; index >= 0; index -= 1) {
siftDown(index, values.length - 1);
}
for (let end = values.length - 1; end > 0; end -= 1) {
[values[0], values[end]] = [values[end], values[0]];
siftDown(0, end - 1);
}
}Después de cada extracción:
heap no ordenado | sufijo ordenadoEl sufijo contiene los mayores elementos en su posición final.
O(n);n - 1 extracciones: O(n log n);O(n log n) en todos los casos;O(1);| Algoritmo | Mejor | Promedio | Peor | Memoria | Estable |
|---|---|---|---|---|---|
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sí, si merge lo conserva |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) promedio | No habitual |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Quick sort suele tener buena localidad de memoria y bajo overhead. Merge sort hace accesos secuenciales, funciona bien con linked lists y external sorting, pero necesita buffer en arrays. Heap sort garantiza memoria mínima, aunque sus saltos por el array suelen aprovechar peor la caché.
Muchos runtimes usan algoritmos híbridos:
Si los datos no caben en memoria:
Merge sort encaja porque la combinación puede procesarse secuencialmente desde disco.
NaN en claves numéricas.shift() y añadir costos de desplazamiento.O(n log n).O(n log n).O(n log n) a cambio de memoria.O(n log n) e in-place, sin estabilidad.¿Por qué elegir un pivot aleatorio mejora quick sort sin cambiar su peor caso teórico?
Porque hace poco probable que una entrada concreta produzca repetidamente particiones extremas, pero todavía existe una secuencia posible de pivots que genera O(n²). Mejora el comportamiento esperado, no elimina el peor caso.