Ver índice de contenidos del libro

20.1. Ordenamiento por mezcla o Merge sort

Este método se basa en la siguiente idea:

  1. Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. De lo contrario hacer lo siguiente:
  2. Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo tamaño cada una.
  3. Ordenar cada una de esas dos sublistas (usando este mismo método).
  4. Una vez que se ordenaron ambas sublistas, intercalarlas de manera ordenada.

Por ejemplo, si la lista original es [6, 7, -1, 0, 5, 2, 3, 8] deberemos ordenar recursivamente [6, 7, -1, 0] y [5, 2, 3, 8] con lo cual obtendremos [-1, 0, 6, 7] y [2, 3, 5, 8]. Si intercalamos ordenadamente las dos listas ordenadas obtenemos la solución buscada: [-1, 0, 2, 3, 5, 6, 7, 8].

Diseñamos la función merge_sort(lista):

  1. Si lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. Se devuelve lista tal cual.
  2. De lo contrario:
    • medio = len(lista)/2
    • izq = merge_sort(lista[:m])
    • der = merge_sort(lista[m:])
    • Se devuelve merge(izq, der).

Falta sólo diseñar la función merge que realiza la intercalación ordenada de dos listas ordenadas (dadas dos listas ordenadas se debe obtener una nueva lista que resulte de intercalar a ambas de manera ordenada).

Diseñamos la función merge(lista1, lista2):

  1. Utilizaremos dos índices, i y j, para recorrer cada una de las dos listas.
  2. Utilizaremos una tercera lista, resultado, donde almacenaremos el resultado.
  3. Mientras i sea menor que el largo de lista1 y j menor que el largo de lista2, significa que hay elementos para comparar en ambas listas.
    • Si el menor es el de lista1: agregar el elemento i de lista1 al final del resultado. Avanzar el índice i.
    • de lo contrario: agregar el elemento j de lista2 al final del resultado. Avanzar el índice j.
  4. Una vez que una de las dos listas se termina, simplemente hay que agregar todo lo que queda en la otra al final del resultado.

El código resultante del diseño de ambas funciones puede verse en el código 20.1.

Nota El método que hemos usado para resolver este problema se llama División y Conquista, y se aplica en las situaciones en las que vale el siguiente principio:

Para obtener una solución es posible partir el problema en varios subproblemas de tamaño menor, resolver cada uno de esos subproblemas por separado aplicando la misma técnica (en nuestro caso ordenar por mezcla cada una de las dos sublistas), y finalmente juntar estas soluciones parciales en una solución completa del problema mayor (en nuestro caso la intercalación ordenada de las dos sublistas ordenadas).

Como siempre sucede con las soluciones recursivas, debemos encontrar un caso base en el cual no se aplica la llamada recursiva (en nuestro caso la base sería el paso 1: Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer). Además debemos asegurar que siempre se alcanza el caso base, y en nuestro caso aseguramos eso porque las lista original se divide siempre en mitades cuando su longitud es mayor que 1.

Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.