Algoritmo MergeSort

Introducción y Descripción del Algoritmo

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:

• [2, 6, 10] + [-1, 3, 12] => [-1, 2, 3, 6, 10, 12]

El algoritmo llama a esto mezclar.

Entonces el algoritmo completo se basa en:

• Caso Base: una lista vacía o de un elemento ya está ordenada
• Regla Recursiva:
  • partir la lista en 2 partes
  • ordenar recursivamente ambas partes
  • luego mezclarlas como vimos arriba.

Ejemplo

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:

Implementación

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:

• ella misma si tiene un solo elemento
• en otro caso, se divide al medio, se aplica el mergeSort de cada parte, y luego se mezclan las ordenadas.

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:

Mezclar Iterando

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.

Mezclar Recursivo con Colas

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:

• en result se va acumulando la lista final mezclada
• Si la primer cola está vacía, entonces símplemente agrega todos los elementos de la segunda a result
• Si la segunda está vacía, agrega todos los de la primera.
• Si ambas tienen elemento entonces agrega un solo elemento a "result", que es el menor entre la cabeza de cada cola, sacándo dicho elemento de la cola (usando popleft()).
• Luego vuelve a llamarse recursivamente con los mismos valores, ya que el popLeft fue el que modificó la cola, una de ella tendrá un elemento menos.

Análisis del Algoritmo

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