Ver índice de contenidos del libro

20.2. ¿Cuánto cuesta el Merge sort?

Sea N la longitud de la lista. Observamos lo siguiente:

  • Para intercalar dos listas de longitud N/2 hace falta recorrer ambas listas que en total tienen N elementos, por lo que es proporcional a N. Llamemos a * N a ese tiempo.
  • Si llamamos T(N) al tiempo que tarda el algoritmo en ordenar una lista de longitud N, vemos que T(N) = 2 * T(N/2) + a * N.
  • Además, cuando la lista es pequeña, la operación es de tiempo constante: T(1) = T(0) = b.
# Código 20.1: mergesort.py: Una implementación de *Merge sort
 
#!/usr/bin/env python
#encoding: latin1
 
def merge_sort(lista):
   """ Ordena lista mediante el método merge sort.
       Pre: lista debe contener elementos comparables.
       Devuelve: una nueva lista ordenada. """
 
   # Una lista de 1 o 0 elementos, ya está ordenada
   if len(lista) < 2:
      return lista
 
   # Si tiene 2 o más elementos, se divide al medio y ordena cada parte
   medio = len(lista) / 2
   izq = merge_sort(lista[:medio])
   der = merge_sort(lista[medio:])
   return merge(izq, der)
 
def merge(lista1, lista2):
   """ Intercala los elementos de lista1 y lista2 de forma ordenada.
       Pre: lista1 y lista2 deben estar ordenadas.
       Devuelve: una lista con los elementos de lista1 y lista2. """
 
   i, j = 0, 0
   resultado = []
 
   # Intercalar ordenadamente
   while(i < len(lista1) and j < len(lista2)):
      if (lista1[i] < lista2[j]):
         resultado.append(lista1[i])
         i += 1
      else:
         resultado.append(lista2[j])
         j += 1
 
   # Agregar lo que falta, si i o j ya son len(lista) no agrega nada.
   resultado += lista1[i:]
   resultado += lista2[j:]
 
   return resultado

Para simplificar la cuenta vamos a suponer que N = 2^k.

T(N) = T(2^k) = 2 * T(2^k−1) + a * 2^k            (20.1)
     = 2 * (2 * T(2^k−2) + a * 2^k-1) + a * 2^k   (20.2)
     = 2^2 * T(2^k−2) + a * 2^k + a * 2^k         (20.3)
       ...                                        (20.4)
     = 2^i * T(2^k−i) + i * a * 2^k               (20.5)
       ...                                        (20.6)
     = 2^k * T(1) + k * a * 2^k                   (20.7)
     = b * 2^k + k * a * 2^k                      (20.8)

Pero si N = 2^k entonces k = log2 N, y por lo tanto hemos demostrado que:

T(N) = b x N + a x N x log2 N                     (20.9)

Como lo que nos interesa es aproximar el valor, diremos (despreciando el término de menor orden) que T(N) = N * log2 N. Hemos mostrado entonces un algoritmo que se porta mucho mejor que los que vimos en la unidad pasada.

Si analizamos el espacio que consume, vemos que a cada paso genera una nueva lista, de la suma de los tamaños de las dos listas, es decir que duplica el espacio consumido.

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.