La idea de este algoritmo es la de dividir el problema en subproblemas más pequeños. Para eso es indispensable utilizar la recursividad.
La idea es que es fácil, dadas dos listas ordenadas cada una, obtener una tercera que tiene todos sus elementos ordenados.
Ejemplo:
El algoritmo llama a esto mezclar.
Entonces el algoritmo completo se basa en:
Veamos un ejemplo paso a paso antes de entrar en la implementación.
Nuestra lista:
[2, 124, 23, 5, 89, -1, 44, 643, 34]
A continuación las llamadas recursivas van a ir anidándose dividiendo la lista y llegando a este punto:
Luego todas las hojas se resuelven fácil porque dijimos que las listas de 1 elemento se consideran ordenadas.
Entonces pasamos a:
Ojo porque acá el símbolo más no significan que se deben concatenar las listas, sino que se deben MEZCLAR, como dijimos antes, mezclar dos listas es generar una tercera que tiene los elementos de ambas, pero ordenados. En este primer paso las mezclas son simples porque son entre listas de un solo elemento.
Resolvemos las mezclas y queda:
Como se ve estamos comenzando a "volver". Ojo, se parece mucho a como era inicialmente al diagrama inicial, pero presten bastante atención porque antes [5,23] estaba desordenado, era [23, 5] y lo mismo para el nodo de [89, -1] y [34, 643].
Ahora sí, todas las hojas están ordenadas, así que volvemos un nivel en cada una:
Resolvemos las mezclas que ahora son un poco más complicadas porque tenemos mezclas de listas de 2 elementos, y otra de 1 + 2 elementos. Queda:
Ahora que tenemos dos ramas ordenadas las subimos (ya falta poco :P)
Resolvemos la nueva mezcla con listas de 2 y 3 elementos:
Ya estan ordenadas así que retornamos:
Y resolviendo esta última mezcla obtenemos el resultado:
Vamos a presentar dos variantes de la implementación. Sin embargo la primer parte del algoritmo es igual para ambas. Lo que cambia es la forma de hacer la mezcla de dos listas.
Entonces, el mergeSort sería:
def mergeSort(lista):
if len (lista) == 1: return lista
izq, der = dividirAlMedio(lista)
return mezclar(mergeSort(izq), mergeSort(der))
def dividirAlMedio(lista):
middle = len(lista) // 2
return lista[0:middle], lista[middle:]
Como vemos es bastante expresiva la implementación, el mergeSort de una lista es:
Es claro entonces que es una función recursiva, en este caso aplicar la recursividad a ambas mitades de la lista.
Ahora, para la implementación del mezclar vamos a mostrar dos casos:
Esta primer versión itera ambas listas y se va quedando con el elemento menor. Como ambas están ordenadas, esto garantiza el orden de la lista resultado. Así va avanzando por la lista que tenía el menor.
def merge(first, second):
mergedList = []
i, j = 0, 0
while i < len(first) and j < len(second):
if first[i] < second[j]:
mergedList.append(first[i])
i += 1
else:
mergedList.append(second[j])
j += 1
mergedList.extend(first[i:])
mergedList.extend(second[j:])
return mergedList
Puede ser que avance más rápido por una que por la otra, o que tengan distinta cantidad de elemento. Por lo que luego del while, se agregan los elementos restantes.
Esta otra implementación utiliza recursividad para mezclar las listas, y en lugar de recorrerlas con índices utiliza la estructura Cola que permite ir consumiendo el próximo elemento.
def mezclar(izq, der):
r = []
mezclarQueues(deque(izq), deque(der), r)
return r
def mezclarQueues(firstQ, secondQ, result):
if isEmpty(firstQ): result.extend(secondQ); return
if isEmpty(secondQ): result.extend(firstQ); return
result.append(firstQ.popleft() if cabeza(firstQ) <= cabeza(secondQ) else secondQ.popleft())
mezclarQueues(firstQ, secondQ, result)
La lógica realmente está en mezclarQueues que es la función recursiva. La otra es símplemente para hacer el llamado más simple, porque mezclarQueues utiliza una semilla y además deberíamos crear Colas para cada lista.
MezclarQueues entonces se define como:
El mergeSort tiene tiempo de ejecución dado por el orden O(n log(n))
Es decir que es bastante más rápido que el Algoritmo Bubbe Sort