3 - MergeSort

MergeSort es un ordenamiento eficiente basado en división y conquista. Divide la lista en mitades, ordena cada parte de forma recursiva y luego las combina manteniendo el orden. Con complejidad O(n log n) y estabilidad, es la opción preferida en escenarios donde la consistencia del orden importa.

3.1 Idea general: dividir, ordenar, mergear

MergeSort crea un árbol binario de subproblemas:

• Divide el array en dos mitades hasta llegar a subarrays de un elemento.
• Ordena cada mitad de forma recursiva.
• Fusiona las dos mitades ordenadas en un solo array ordenado.

3.2 División recursiva de la lista

La clave está en partir el problema a la mitad hasta llegar al caso base:

def mergesort(valores, inicio, fin):
  if inicio >= fin:
    return
  medio = (inicio + fin) // 2
  mergesort(valores, inicio, medio)
  mergesort(valores, medio + 1, fin)
  merge(valores, inicio, medio, fin)

Cada llamada recursiva trabaja sobre un rango definido por índices inclusivos.

3.3 Función merge()

La función de mezcla toma dos mitades ordenadas y produce una salida ordenada en un buffer auxiliar, luego copia el resultado a la lista original:

def merge(valores, inicio, medio, fin):
  buffer = []
  i = inicio
  j = medio + 1
  while i <= medio and j <= fin:
    if valores[i] <= valores[j]:
      buffer.append(valores[i])
      i += 1
    else:
      buffer.append(valores[j])
      j += 1
  while i <= medio:
    buffer.append(valores[i])
    i += 1
  while j <= fin:
    buffer.append(valores[j])
    j += 1
  valores[inicio:fin + 1] = buffer

El tamaño del buffer siempre coincide con el segmento a mezclar, evitando desbordes y manteniendo la estabilidad.

3.4 Ordenamiento estable

MergeSort preserva el orden relativo de elementos equivalentes porque al mezclar toma primero el elemento de la izquierda cuando son iguales (<= en la comparación). Esta propiedad es clave en reportes, agrupaciones y operaciones de deduplicación.

3.5 Uso de memoria adicional (O(n))

La mezcla necesita espacio auxiliar proporcional al tamaño del segmento a combinar. En entornos críticos de memoria es común reutilizar un buffer global o alternar entre dos arrays para reducir copias.

3.6 Implementación recursiva en Python

Para evitar crear listas nuevas en cada mezcla, usamos un buffer auxiliar reutilizable:

def merge_with_buffer(arr, buffer, inicio, medio, fin):
  i = inicio
  j = medio + 1
  k = inicio
  while i <= medio and j <= fin:
    if arr[i] <= arr[j]:
      buffer[k] = arr[i]
      i += 1
    else:
      buffer[k] = arr[j]
      j += 1
    k += 1
  while i <= medio:
    buffer[k] = arr[i]
    i += 1
    k += 1
  while j <= fin:
    buffer[k] = arr[j]
    j += 1
    k += 1
  arr[inicio:fin + 1] = buffer[inicio:fin + 1]

def mergesort_rec(arr, buffer, inicio, fin):
  if inicio >= fin:
    return
  medio = (inicio + fin) // 2
  mergesort_rec(arr, buffer, inicio, medio)
  mergesort_rec(arr, buffer, medio + 1, fin)
  merge_with_buffer(arr, buffer, inicio, medio, fin)

El buffer se pasa a todas las llamadas y se escribe el resultado ordenado directamente en la lista original.

3.7 MergeSort "top-down"

La versión recursiva clásica reserva el buffer una sola vez y lo comparte:

def mergesort_topdown(arr):
  if not arr:
    return
  buffer = [0] * len(arr)
  mergesort_rec(arr, buffer, 0, len(arr) - 1)

Esta estrategia reduce la sobrecarga de reservas y mantiene la estabilidad del algoritmo.

3.8 MergeSort "bottom-up" (iterativo)

La variante iterativa evita recursión. Recorre la lista en runs de tamaño creciente y mezcla pares adyacentes:

def mergesort_bottomup(arr):
  n = len(arr)
  size = 1
  while size < n:
    inicio = 0
    while inicio < n - size:
      medio = inicio + size - 1
      fin = min(inicio + 2 * size - 1, n - 1)
      merge(arr, inicio, medio, fin)
      inicio += 2 * size
    size *= 2

Resulta práctico cuando se desea controlar el consumo de pila o instrumentar el algoritmo paso a paso. Para minimizar reservas, se puede usar un buffer compartido igual que en la versión top-down.

3.9 Complejidad temporal y espacial

• Tiempo: O(n log n) en peor, promedio y mejor caso.
• Memoria: O(n) espacio adicional para el buffer de mezcla.
• Estabilidad: estable siempre que la mezcla respete el orden de iguales.

3.10 Ventajas y desventajas

• Ventajas: complejidad garantizada O(n log n) incluso en el peor caso; estabilidad; buen comportamiento en datos parcialmente ordenados; estructura clara para paralelizar la fase de división.
• Desventajas: requiere memoria adicional; las copias pueden impactar en caché; no es in-place salvo optimizaciones avanzadas.

3.11 Casos ideales de uso

• Listas enormes: garantiza rendimiento y estabilidad sin sorpresas en el peor caso.
• Datos parcialmente ordenados: la mezcla aprovecha runs existentes y mantiene el orden relativo.
• Ordenamiento externo: la estrategia de mezcla secuencial se adapta bien a archivos y flujos.

MergeSort es un punto de partida excelente para comprender ordenamientos eficientes: muestra cómo dividir y combinar de forma sistemática y establece un rendimiento predecible.

3.12 Archivo único para MergeSort

Para seguir el enfoque del tutorial, todo el algoritmo vive en un solo archivo ordenamientos.py:

# archivo: ordenamientos.py
def merge(valores, inicio, medio, fin):
  buffer = []
  i = inicio
  j = medio + 1
  while i <= medio and j <= fin:
    if valores[i] <= valores[j]:
      buffer.append(valores[i])
      i += 1
    else:
      buffer.append(valores[j])
      j += 1
  while i <= medio:
    buffer.append(valores[i])
    i += 1
  while j <= fin:
    buffer.append(valores[j])
    j += 1
  valores[inicio:fin + 1] = buffer

def mergesort(valores, inicio, fin):
  if inicio >= fin:
    return
  medio = (inicio + fin) // 2
  mergesort(valores, inicio, medio)
  mergesort(valores, medio + 1, fin)
  merge(valores, inicio, medio, fin)

datos = [42, 7, 18, 3, 25]
mergesort(datos, 0, len(datos) - 1)
print(datos)

Con este archivo puedes ejecutar, depurar y comparar resultados sin configuraciones adicionales.