Este método se basa en la siguiente idea:
- 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:
- Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo tamaño cada una.
- Ordenar cada una de esas dos sublistas (usando este mismo método).
- 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):
- 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.
- De lo contrario:
medio = len(lista)/2izq = 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):
- Utilizaremos dos índices,
iyj, para recorrer cada una de las dos listas. - Utilizaremos una tercera lista, resultado, donde almacenaremos el resultado.
- Mientras
isea menor que el largo delista1yjmenor que el largo delista2, significa que hay elementos para comparar en ambas listas.- Si el menor es el de
lista1: agregar el elementoidelista1al final del resultado. Avanzar el índicei. - de lo contrario: agregar el elemento
jdelista2al final del resultado. Avanzar el índicej.
- Si el menor es el de
- 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.