Mergesort 02 - Complejidad de Mergesort

Versión corta:

Para una lista de tamaño n Mergesort se autoinvoca O(logn) para llegar a n listas de tamaño 1.
Luego debe realizar O(logn) merges hasta obtener una lista del mismo tamaño original. Cada merge cuesta O(n).
Por lo tanto es O(n logn)

Versión larga:

MergeSort(A):
  if (len(A) > 1)
     split into two subarrays
     call Mergesort(Aleft) , Mergesort(Aright)
     merge(Aleft, Aright)

Caso base: T(1) = a. El tiempo para un arreglo de tamaño 1 es constante.
Caso recursivo: T(n) = b + 2T(n/2) + n, i.e. el tiempo para un arreglo mayor de 1 es el tiempo constante de separarlo en dos subarreglos (b), llamar a mergesort sobre los dos subarreglos (el término 2T(n/2)) y el tiempo necesario para hacer merge sobre los dos subarreglos (n)
La forma cerrada de esa relación de recurrencia es

$T(n) = (n-1) \cdot b + n \cdot a + n \cdot \log_2(n)$