Merge sort (ordenamiento por mezcla): cómo funciona, código y complejidad

La idea en palabras sencillas

Una lista con cero o un elemento ya está ordenada. Para una lista más larga:

1. Dividir: separa la lista en una mitad izquierda y una mitad derecha.
2. Vencer: ordena cada mitad con merge sort.
3. Combinar: mezcla las dos mitades ordenadas. Compara el primer elemento de cada una, pasa el menor a la salida y repite hasta que una mitad quede vacía; entonces copia lo que quede de la otra.

Todo el trabajo real ocurre en el paso de mezcla, y mezclar dos listas ordenadas de longitud total n requiere como máximo n − 1 comparaciones.

Ejemplo resuelto, paso a paso

Ordena [38, 27, 43, 3, 9, 82, 10].

La mezcla final compara los primeros elementos: 27 contra 3 toma 3, 27 contra 9 toma 9, 27 contra 10 toma 10, 27 contra 82 toma 27, 38 contra 82 toma 38, 43 contra 82 toma 43 y después se copia 82. Seis comparaciones para siete elementos.

Implementación en Python

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

Esta versión descendente (top-down) es clara pero copia rebanadas. Una versión ascendente (bottom-up) evita por completo la recursión: mezcla tramos de anchura 1, luego 2, luego 4, y así sucesivamente.

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

La versión ascendente reutiliza merge del código anterior. La biblioteca estándar también tiene heapq.merge, que mezcla de forma perezosa cualquier cantidad de iterables ordenados.

Complejidad temporal y espacial

La recurrencia es T(n) = 2T(n/2) + O(n). Cada nivel del árbol de recursión hace O(n) de trabajo en total y hay unos log₂ n niveles, así que el total es O(n log n). Para un millón de elementos son unos 20 niveles.

Cómo se compara merge sort con otros ordenamientos

Merge sort es estable porque la mezcla toma de la mitad izquierda cuando dos elementos son iguales, así que los elementos iguales conservan su orden. En comparación con quicksort, tiene un peor caso O(n log n) garantizado, pero necesita O(n) de memoria adicional y, en arreglos, suele mover más datos. En comparación con heapsort, es estable y accede a la memoria de forma secuencial, lo que favorece a las cachés y a los discos.

Variantes y errores comunes

• Natural merge sort detecta los tramos que ya están ordenados y los mezcla, con lo que logra O(n) con entradas ordenadas. Timsort es un natural merge sort refinado que usa insertion sort binario para los tramos cortos.
• Cambia a insertion sort en las sublistas pequeñas (por ejemplo, de menos de unos 10 a 30 elementos) para reducir la sobrecarga.
• En listas enlazadas, merge sort no necesita búfer adicional: la mezcla solo reenlaza nodos, por lo que es la opción habitual para ordenar una lista enlazada.
• El merge sort externo ordena fragmentos que caben en memoria, los escribe en disco y luego realiza una mezcla de k vías. Las bases de datos y herramientas como sort de GNU usan esta idea con archivos grandes.
• Contar inversiones: durante la mezcla, cada vez que se toma un elemento de la mitad derecha, este es menor que todos los elementos restantes de la mitad izquierda.

Cuándo usar merge sort

Elige merge sort cuando necesites un ordenamiento estable con un tiempo O(n log n) garantizado, cuando ordenes listas enlazadas o cuando los datos sean demasiado grandes para la memoria. En Python, basta con llamar a sorted() o list.sort(): implementan Timsort, que es una variante de merge sort, así que ya obtienes estas propiedades. Escribir merge sort a mano es un ejercicio clásico de entrevista, a menudo ampliado a contar inversiones o a mezclar k listas ordenadas.