Algoritmos: ¿Cómo la combinación de ordenamiento tiene complejidad espacial O (n) para el peor de los casos?

Mergesort, si se implementa para crear matrices en las llamadas recursivas, creará muchas de ellas, pero no coexistirán al mismo tiempo. En cada llamada recursiva, crea una matriz (o 2 dependiendo de una implementación) para fusionar y no ocupan más que O (n) espacio, y luego, cuando se realiza la fusión, estas matrices se eliminan y se crearán algunas nuevas después de un momento en alguna otra llamada recursiva. Si contó cuánto espacio ocuparon todos los arreglos que alguna vez se crearon, sería O (n log n), pero no necesita preocuparse por esta información; no necesita más que O (n) espacio, porque cuando necesita crear una matriz, todos los demás ya no existen y no ocupan memoria. Tenga en cuenta que simplemente puede declarar 2 o 3 matrices al principio, cada una de la longitud de n, y luego almacenar la secuencia en una de ellas, mientras usa la otra para fusionar, mejorará el rendimiento y le mostrará más allá dudo que no haya necesidad de más de O (n) de memoria.