Mejor respuesta
La ordenación por fusión, si se implementa para crear matrices en las llamadas recursivas, creará muchos de ellos, pero no coexistirán al mismo tiempo. En cada llamada recursiva, creas una matriz (o 2 dependiendo de una implementación) para fusionar y no ocupan más de O (n) espacio, y luego cuando la fusión hecho, estas matrices se eliminan y algunas nuevas se crearán después de un momento en alguna otra llamada recursiva. Si contaras cuánto espacio ocuparon todas las matrices 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, todas las demás ya no existen y no ocupan memoria . Tenga en cuenta que puede simplemente 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.
Respuesta
En la clasificación por fusión cuando estamos fusionando la matriz ordenada 2 creamos 2 matriz temporal. L [ ] = Arr [izquierda, mitad] (matriz izquierda) para almacenar temporalmente la matriz anterior de izquierda a media (mitad izquierda ordenada) y R [] = Arr [mitad + 1, derecha] (matriz derecha) para almacenar temporalmente la matriz anterior de mid + 1 a la derecha (ordenados por la mitad derecha), luego fusionamos las dos matrices temporales en la original. El hecho de que creamos 2 matrices temporales para almacenar los números de la matriz original, ya que la matriz original tiene n elementos, la matriz temporal las matrices son de tamaño n respectivamente y, por lo tanto, el espacio extra de n y una complejidad de espacio O (n). El espacio original de la matriz no se tiene en cuenta al calcular la complejidad espacial de una clase algoritmo de ing.