Traza completa de Merge Sort

Enunciado

Dado el siguiente arreglo:

$A = [38, 27, 43, 3, 9, 82, 10]$

(a) Realice una traza completa del algoritmo Merge Sort, mostrando:

1. Todas las divisiones recursivas del arreglo (arbol de llamadas recursivas).
2. Cada paso de fusion (merge), indicando como se combinan los subarreglos ordenados.
3. El arreglo resultante en cada nivel del arbol de recursion.

(b) Cuantas llamadas recursivas se realizan en total (incluyendo la llamada inicial)?

(c) Cuantas comparaciones se realizan durante todas las operaciones de merge combinadas?

(d) La complejidad temporal de Merge Sort es $O(n \log n)$ en todos los casos. Explique por que, haciendo referencia a:

• Cuantos niveles tiene el arbol de recursion (en funcion de $n$).
• Cuanto trabajo se realiza en cada nivel.

(e) Cual es la complejidad espacial de Merge Sort? Por que no se considera un algoritmo in-place?