Ordenamiento por mezcla y «divide y vencerás»

Código en:JavaC#PythonJavaScript

En resumen: El ordenamiento por mezcla divide la lista en mitades hasta elementos sueltos y las une de nuevo en orden: O(n log n) comparaciones con cualquier entrada, a costa de O(n) de memoria extra.

Problema

«Ordenar por precio» con 100.000 productos

La tienda en línea ha crecido hasta 100 000 productos. El botón «Ordenar por precio» usa el ordenamiento por inserción de los ordenamientos simples.

Con 1000 productos, el ordenamiento por inserción hace 256.555 comparaciones, y la página se abre enseguida. Con 100 000 las comparaciones son unos 2500 millones. Los productos son 100 veces más, y el trabajo es 10 000 veces mayor: el ordenamiento por inserción es O(n²), porque cada precio nuevo puede compararse con todos los anteriores.

Necesitas una forma en la que el doble de productos dé algo más del doble de trabajo.

La idea

Divide y vencerás

¿Cómo ordenan dos personas un montón de 1000 facturas por importe? Lo dividen en dos, cada una ordena su mitad, y luego las mezclan: miran la factura de arriba de los dos montones y toman la menor. Mezclar dos montones ordenados es rápido: cada comparación pone una factura en su lugar.

¿Y cómo ordena cada una su mitad? Igual: la divide en dos. Y así hasta que queda una factura. Una factura ya está ordenada.

Esto es divide y vencerás: la tarea se divide en tareas más pequeñas del mismo tipo, se resuelven con el mismo método y sus respuestas se juntan. Un ordenamiento hecho así es el ordenamiento por mezcla (merge sort).

El método se llama a sí mismo, así que esto es recursión, como en la lección «Recursión». El caso base es una lista con un precio: no hay nada que dividir.

Míralo

Divide hasta un precio y une de nuevo

merge_sort divide y se llama a sí mismo para las dos mitades. merge une dos partes ordenadas. Mira cómo los ocho precios bajan hasta quedar sueltos y cómo las mezclas los ordenan al volver:

def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    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:])
    merged.extend(right[j:])
    return merged

Paso a paso, en palabras

1. merge_sort recibe 8 precios del catálogo, sin orden.
2. mid = 4. El slice [:mid] crea dos listas nuevas: la mitad izquierda [45, 12, 80, 33] y la mitad derecha [7, 61, 25, 50].
3. Cada mitad llama a merge_sort para sí misma y se divide otra vez: 4 → 2 → 1.
4. Una parte con un precio ya está ordenada. Es el caso base: a partir de aquí las llamadas empiezan a volver.
5. merge une dos partes ordenadas: compara sus primeros precios y toma el menor. Para un par es 1 comparación: 4 en toda la fila.
6. Los pares pasan a ser grupos de cuatro. Cada comparación manda un precio hacia abajo, así que una fila nunca necesita más comparaciones que precios tiene: aquí 6.
7. La última mezcla, [12, 33, 45, 80] con [7, 25, 50, 61]. i y j apuntan al primer precio aún no tomado de cada lado: 7 comparaciones, 7 precios.
8. Un lado se ha acabado. Lo que queda del otro (80) ya está ordenado y va al final sin comparar.
9. 3 niveles de división (8 → 4 → 2 → 1), y en cada nivel la mezcla pasa una vez por cada precio: 4 + 6 + 7 = 17 comparaciones. Con n precios hay log₂ n niveles, así que el trabajo es de unas n · log₂ n.

prices = [45, 12, 80, 33, 7, 61, 25, 50]
print(f"Antes: {prices}")
print(f"Después: {merge_sort(prices)}")

Salida

Antes: [45, 12, 80, 33, 7, 61, 25, 50]
Después: [7, 12, 25, 33, 45, 50, 61, 80]

prices[:mid] es un slice: una lista nueva con los elementos desde 0 hasta mid (sin incluirlo). // divide y redondea hacia abajo, así que mid es 4 incluso con 9 precios.

La idea

Por qué es n · log n

Mira cuánto cuesta cada parte:

• Mezclar es O(n). Cada comparación pone un precio en el resultado, y cuando una parte se acaba, el resto de la otra va al final sin comparar. Dos partes con n precios en total necesitan como máximo n − 1 comparaciones.
• Hay log₂ n niveles. Cada nivel reduce a la mitad: 8 precios dan 3 niveles (8 → 4 → 2 → 1), 100 000 precios dan 17. log₂ n es «cuántas veces se divide n por la mitad hasta llegar a 1».
• En cada nivel las mezclas pasan una vez por los n precios. Pares, grupos de cuatro, mitades: los grupos cambian de un nivel a otro, pero juntos siempre son n.

En total: como máximo n · log₂ n comparaciones. Con 100 000 precios son menos de 1 700 000. Bench cuenta 1.536.292, unas 1600 veces menos que los 2500 millones del ordenamiento por inserción.

Pruébalo

Predice la salida

Aquí merge cuenta sus comparaciones. Las dos partes están ordenadas, y cada precio de la izquierda es menor que cada precio de la derecha:

comparisons = 0


def merge(left, right):
    global comparisons
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


print(merge([10, 20, 30], [40, 50, 60]))
print(f"Comparaciones: {comparisons}")

Respuesta

[10, 20, 30, 40, 50, 60]
Comparaciones: 6

[10, 20, 30, 40, 50, 60]
Comparaciones: 3

[10, 20, 30, 40, 50, 60]
Comparaciones: 5

Comprobar

Míralo

Mídelo: mezcla contra inserción

Ejecuta los dos algoritmos con el mismo catálogo de precios. Lo que se cuenta son comparaciones. El ordenamiento por inserción no se ejecuta de verdad con 100 000 (la página se congelaría): Bench lo estima a partir de la curva.

• Ordenamiento por inserción O(n²)
• Ordenamiento por mezcla O(n log n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Ordenamiento por inserción	32	256.555	24.738.716	≈ 2.473.871.600
Ordenamiento por mezcla	24	8679	120.483	1.536.292

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    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:])
    merged.extend(right[j:])
    return merged

Con 10 precios los dos son casi iguales. Con 1000, el ordenamiento por mezcla hace 8679 comparaciones contra 256.555. A partir de ahí la brecha crece con cada cero: la curva O(n²) es el doble de empinada.

Más precisamente, para curiosos

Los mismos números en tu lenguaje. El catálogo sale de un pequeño generador con semilla, así que es el mismo en cada ejecución, en cada lenguaje y en Bench. El contador sube en cada comparación de dos precios:

comparisons = 0


def catalog(n):
    prices = []
    x = 2026
    for _ in range(n):
        x = x * 48271 % 2147483647
        prices.append(1 + x % 10000)
    return prices


def insertion_sort(prices):
    global comparisons
    for i in range(1, len(prices)):
        key = prices[i]
        j = i
        while j > 0:
            comparisons += 1
            if prices[j - 1] <= key:
                break
            prices[j] = prices[j - 1]
            j -= 1
        prices[j] = key


def merge_sort(prices):
    if len(prices) <= 1:
        return prices
    mid = len(prices) // 2
    left = prices[:mid]
    right = prices[mid:]
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    global comparisons
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


for n in [10, 1000]:
    comparisons = 0
    insertion_sort(catalog(n))
    print(f"insertion sort, n = {n}: {comparisons} comparaciones")
for n in [10, 1000, 100000]:
    comparisons = 0
    merge_sort(catalog(n))
    print(f"merge sort, n = {n}: {comparisons} comparaciones")

Salida

insertion sort, n = 10: 32 comparaciones
insertion sort, n = 1000: 256555 comparaciones
merge sort, n = 10: 24 comparaciones
merge sort, n = 1000: 8679 comparaciones
merge sort, n = 100000: 1536292 comparaciones

La idea

El precio: memoria

El ordenamiento por mezcla no es gratis. El de inserción mueve los precios dentro de la propia lista y no necesita otro espacio. El de mezcla crea listas nuevos en cada división, y merge escribe el resultado en uno más. La memoria extra es O(n): con 100 000 precios, otro tanto de espacio.

La pila de llamadas es poco profunda: un marco por nivel, unos log₂ n. Con 100 000 precios son 18 marcos.

Los precios iguales se quedan en el orden en que llegaron: en un empate merge toma el de la izquierda (<=). Esto se llama estabilidad, y tiene su propia lección, «Ordenamiento estable y el ordenamiento incorporado».

En Python el slice prices[:mid] siempre crea una lista nueva. Así que este ordenamiento por mezcla es corto, pero copia mucho. El sorted incorporado es TimSort, una variante del ordenamiento por mezcla escrita en C, y es mucho más rápido.

Pruébalo

Encuentra el error

Entra un catálogo de ocho productos, y salen cuatro:

prices = [45, 12, 80, 33, 7, 61, 25, 50]
print(f"Antes: {prices}")
print(f"Después: {merge_sort(prices)}")

Salida

Antes: [45, 12, 80, 33, 7, 61, 25, 50]
Después: [33, 45, 50, 61]

¿En qué línea está el error?

Elige la línea con el error.

1def merge_sort(prices):2 if len(prices) <= 1:3 return prices4 mid = len(prices) // 25 left = prices[:mid]6 right = prices[mid + 1:]7 return merge(merge_sort(left), merge_sort(right))

Comprobar

Pruébalo

Rellena el hueco

El bucle de merge se detiene en cuanto una parte se acaba. ¿Qué va en el hueco para que el resto de la parte derecha vaya al final?

def merge(left, right):
    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:])
    merged.extend(right[:])
    return merged

Comprobar

Ejercicio

Dos almacenes, una lista de precios

Resuelve la tarea en tu editor.

Dos almacenes. El almacén de Sofía y el almacén de Varna envían sus listas de precios, cada una ya ordenada. Lee las dos líneas e imprime una lista de precios ordenada para ambos. No ordenes otra vez: usa merge de la lección. El trabajo es O(n), no O(n log n).

Entrada

12 33 45 80
7 25 50 61 99

Salida

Total: 7 12 25 33 45 50 61 80 99

Más tareas

• Contar. Añade un contador de comparaciones a merge y ordena los ocho precios de la escena. Deberías obtener 17.
• El más caro primero. Cambia un signo para que la lista salga del más caro al más barato.
• Sin recursión. Une los precios sueltos vecinos en pares, luego los pares en grupos de cuatro, luego los de cuatro. Es el ordenamiento por mezcla ascendente (bottom-up): las mismas comparaciones, sin pila de llamadas.

Más precisamente

Mezclar fuera del ordenamiento

Mezclar listas ordenadas es más antiguo que el ordenamiento por mezcla: las máquinas de tarjetas perforadas ya mezclaban mazos de tarjetas ordenados en la década de 1930. Hoy aparece en cualquier sitio donde los datos ya están ordenados: en git, en las bases de datos, en archivos más grandes que la memoria.

Más precisamente, para curiosos

Git. Git guarda el contenido de cada carpeta (un árbol) ordenado por nombre de archivo. Cuando compara dos versiones o une ramas, recorre las dos listas ordenadas lado a lado, como merge: un nombre que solo está en un lado es un archivo añadido o borrado, y los nombres iguales son un archivo en ambos lados, que se compara. Así que revisar una carpeta es O(n), no una búsqueda de cada archivo en la otra lista. Unir el texto dentro de un archivo es otro algoritmo (diff), al que llegamos en el módulo «Programación dinámica».

Ordenamiento externo. Los registros del sitio de un año son 50 GB, y la memoria es de 8 GB. El ordenamiento lee 1 GB cada vez, lo ordena en memoria y lo escribe como un bloque ordenado en el disco. Luego mezcla los bloques: de cada uno lee solo la primera línea, toma la menor y sigue. La memoria alcanza para una línea de cada bloque. Así ordena archivos grandes el comando sort de Linux, y PostgreSQL escribe Sort Method: external merge en el plan de la consulta cuando el ordenamiento no cabe en su memoria.

El teorema maestro, como intuición. El tiempo del ordenamiento por mezcla se escribe T(n) = 2 · T(n/2) + n: dos tareas de la mitad del tamaño más n por la mezcla. Dibújalo como un árbol: arriba hay n de trabajo, en el nivel siguiente dos veces n/2, que otra vez es n, y así durante log₂ n niveles. En total n · log₂ n. El teorema maestro generaliza justo esta comparación: si el trabajo por nivel se reduce hacia abajo, decide el nivel de arriba; si crece, deciden las hojas; si es igual en cada nivel, multiplicas por el número de niveles. La búsqueda binaria es T(n) = T(n/2) + 1: 1 por nivel, log₂ n niveles, O(log n).

El ordenamiento incorporado. En Python sorted y list.sort usan TimSort, una variante del ordenamiento por mezcla que encuentra los tramos ya ordenados de la entrada. Cómo y por qué está en la lección «Ordenamiento estable y el ordenamiento incorporado».

Test

Ponte a prueba

1. ¿Por qué el ordenamiento por mezcla es O(n log n)?

Divide en dos, y dividir en dos es log nDividir da log₂ n niveles, y la mezcla de cada nivel pasa una vez por los n preciosCompara cada precio con todos los demás, pero solo una vez

2. merge une dos partes ordenadas de 4 precios cada una. ¿Cuántas comparaciones hace como máximo?

1687

3. ¿Qué paga el ordenamiento por mezcla que el de inserción no paga?

No puede ordenar precios igualesMás comparaciones con un n grandeMemoria: las copias de las mitades y el resultado mezclado, O(n) extra

4. Los ocho precios ya están ordenados. ¿Cuántas comparaciones hace cada uno?

7 cada unoInserción 7, mezcla 12Inserción 28, mezcla 17

5. ¿Cuántos niveles de división tiene el ordenamiento por mezcla con 100 000 precios?

100 00050 00017

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Big-O: cómo crece el trabajo · Mejor caso, caso promedio y peor caso · Complejidad en espacio · Ordenamiento por inserción y por selección
• Continúa en: Quicksort y el mal pivote · Montículo y ordenamiento por montículo · Ordenamiento por conteo y radix · Ordenamiento estable y el ordenamiento incorporado
• Ejercicios sobre el tema: Ordenamiento