Mergesort 01

Preguntas relacionadas con el video:

1. El presentador menciona que una de las formas de hacer merge de dos listas ordenadas sería concatenar una de ellas al final de la otra y aplicar algún tipo de sorting. ¿Por qué esa estrategia NO es recomendable?

2. Otro método (erróneo) de hacer merge a dos listas ordenadas es barajarlas, i.e. dado L1 y L2, para construir L3 alternamos entre insertar un elemento de L1 y luego uno de L2 hasta que vaciemos ambas listas.

   1. Muestra dos listas para las cuales esa estrategia produciría un resultado correcto.
   2. Muestra dos listas para las que produciría un resultado incorrecto.

3. Usando un estilo como el que muestra esta página muestra cómo funciona merge sobre las siguientes dos listas: L1 = 4, 5, 10 y L2 = 1, 8, 9.

4. En el peor de los casos, ¿cuántas comparaciones entre enteros haría falta hacer merge de dos listas ordenadas de 1000 enteros cada una?

5. ¿Mergesort sirve para listas que tengan un número impar de elementos? Si es así, que hacemos con las sublistas que no quedan de igual tamaño.

6. ¿Es mergesort un algoritmo naturalmente inline?

7. ¿Qué consideración es importante si queremos que mergesort sea un algoritmo estable? Por ejemplo, si A = 5, 2, 3, 2, ¿cómo garantizamos que el primer 2 queda antes que el segundo 2 en el resultado.