Merge sort: dividir, ordenar y combinar
Implemente merge sort de forma recursiva, trace el árbol de divide y vencerás y explique por qué garantiza O(n log n) en todos los casos.
Merge sort: dividir, ordenar y combinar es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Intuición de divide y vencerás
Merge sort es un algoritmo clásico de divide y vencerás: divida el arreglo por la mitad, ordene recursivamente cada mitad y, después, mezcle las dos mitades ordenadas en un único resultado ordenado. La idea clave es que mezclar dos arreglos ordenados requiere O(n), un coste muy inferior al de ordenar desde cero. Esta descomposición produce un árbol de recursión con log n niveles, cada uno de los cuales requiere O(n) de trabajo de mezcla, lo que proporciona la cota óptima de O(n log n) para los algoritmos de ordenación por comparación.
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Explicación del paso de mezcla
Para mezclar dos arreglos ordenados, mantenga dos punteros, uno para cada mitad. Compare los elementos iniciales; copie el menor en la salida y avance el puntero correspondiente. Cuando una mitad se agote, copie directamente el resto de la otra mitad. Esto requiere O(n) de tiempo y O(n) de espacio para el arreglo de salida. El paso de mezcla es el núcleo algorítmico de merge sort; debe comprenderlo a fondo.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Implementación completa de Merge Sort
Al combinar la división y la mezcla: las llamadas recursivas dividen el problema por la mitad hasta que solo quedan elementos individuales (trivialmente ordenados); después, las llamadas de mezcla los vuelven a combinar. Cada nivel del árbol de recursión mezcla en total los mismos n elementos (distribuidos entre varias mezclas). La profundidad de la recursión es log₂(n), lo que produce un tiempo total O(n log n) y un espacio auxiliar O(n) para los arreglos de salida de la mezcla, además de una profundidad de pila de llamadas O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Árbol de recursión de Merge Sort
Visualice el árbol de recursión de merge sort para n=8: el nivel 0 tiene un arreglo de 8 elementos; el nivel 1 tiene dos arreglos de 4; el nivel 2 tiene cuatro de 2; el nivel 3 tiene ocho elementos individuales (casos base). Al volver hacia arriba, en el nivel 3→2 se mezclan 8 elementos en total, en el nivel 2→1 se mezclan 8 en total y en el nivel 1→0 se mezclan 8 en total. Esto equivale a 3 niveles × 8 elementos = 24 operaciones ≈ 8 × log₂(8) = 24. Esto confirma O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Merge Sort in-place
El merge sort recursivo estándar asigna un espacio auxiliar O(n) para la salida de la mezcla. Existe un merge sort in-place, pero es complejo y tiene factores constantes altos; rara vez se pregunta por él en entrevistas. La pregunta de seguimiento habitual en entrevistas es: '¿Puede hacer merge sort con O(1) de espacio adicional?' La respuesta correcta es: 'En teoría, sí, pero las implementaciones prácticas sacrifican el espacio O(n) o añaden complejidad; el Timsort de Python usa espacio O(n) para la mezcla.'
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Merge Sort es estable
Merge sort es estable: los elementos iguales de la mitad izquierda siempre aparecen antes que los elementos iguales de la mitad derecha en la salida combinada. Esto se garantiza usando <= (no <) al dar preferencia al elemento izquierdo. La estabilidad es importante para ordenar por varias claves. Las funciones integradas sorted() y list.sort() de Python usan Timsort, que también es estable y O(n log n), por lo que son la opción segura para todo el código de producción.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Mezclar k arreglos ordenados
Mezclar k arreglos ordenados con un total de n elementos se puede hacer mezclando repetidamente pares (como en un cuadro de torneo), en un tiempo O(n log k). Cada nivel de mezcla procesa n elementos y hay log k niveles. Como alternativa, use un montículo mínimo de tamaño k: inserte el elemento restante más pequeño de cada arreglo, extraiga el mínimo e inserte el siguiente elemento de ese arreglo. El enfoque del montículo también es O(n log k), pero usa menos memoria cuando k es muy grande.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Contar inversiones con Merge Sort
Contar inversiones (pares en los que a[i] > a[j] e i < j) en O(n log n) requiere un merge sort modificado. Durante el paso de mezcla, cuando un elemento del subarreglo derecho es menor que un elemento del subarreglo izquierdo, forma una inversión con cada elemento restante del subarreglo izquierdo. En ese momento, añada len(left) - i al contador.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Merge Sort frente a Quick Sort
Merge sort garantiza O(n log n) en todos los casos, es estable y es la mejor opción para listas enlazadas y ordenamiento externo. Quick sort tiene un caso promedio O(n log n), pero un peor caso O(n²); es in-place (con espacio de pila O(log n)) y suele ser más rápido en la práctica gracias a la eficiencia de caché en los arreglos. El ordenamiento integrado de Python usa Timsort (una variante de merge sort), que siempre es la opción predeterminada adecuada.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Ordenamiento externo: Merge Sort a gran escala
Merge sort es el algoritmo que sustenta el ordenamiento externo (ordenar datos demasiado grandes para caber en la RAM). Los datos se leen en bloques, cada bloque se ordena en memoria y los bloques se mezclan desde el disco. El paso de mezcla lee un elemento a la vez de cada secuencia ordenada, manteniendo en memoria solo O(k) elementos simultáneamente (uno por secuencia). Por eso merge sort se usa en bases de datos, Hadoop MapReduce y los algoritmos clásicos de ordenamiento en cinta.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Resumen de Merge Sort y consejos para entrevistas
En las entrevistas, implementar merge sort de forma clara demuestra que comprende la recursión, el paso de mezcla y la estrategia de divide y vencerás. Preguntas de seguimiento habituales:
- ¿Por qué O(n log n) y no O(n²)? (log n niveles × n operaciones por nivel)
- ¿Es estable? (Sí, use <= en la mezcla)
- ¿Cuánto espacio utiliza? (O(n) auxiliar + pila O(log n))
- ¿Puede hacerlo de forma iterativa? (Sí, con merge sort ascendente)
- ¿Cómo lo usaría con una lista enlazada? (Es más fácil que con un arreglo, porque no hay un costo de división O(n); use punteros lento y rápido para encontrar el punto medio)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Recapitulación de la lección
En esta lección aprendió que: merge sort divide el arreglo por el punto medio, ordena recursivamente cada mitad y mezcla las dos mitades ordenadas en O(n), lo que produce un tiempo total O(n log n) a lo largo de log n niveles de recursión; el paso de mezcla usa <= para tomar el elemento izquierdo en caso de empate, lo que garantiza la estabilidad; y merge sort es el algoritmo de preferencia para listas enlazadas, ordenamiento externo y situaciones en las que se requiere estabilidad, mientras que quick sort se prefiere para arreglos en memoria cuando el espacio es limitado. A continuación implementaremos quick sort y exploraremos estrategias para elegir el pivote.
Preguntas frecuentes
¿La lección «Merge sort: dividir, ordenar y combinar» es gratis?
Sí — el texto completo de «Merge sort: dividir, ordenar y combinar» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Merge sort: dividir, ordenar y combinar»?
Implemente merge sort de forma recursiva, trace el árbol de divide y vencerás y explique por qué garantiza O(n log n) en todos los casos. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Merge sort: dividir, ordenar y combinar»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Bubble sort e insertion sort
- Merge sort: dividir, ordenar y combinar
- Quick sort y selección del pivote
- Ordenaciones sin comparación y sort() de Python