Melhor resposta
O Mergesort, se implementado para criar matrizes nas chamadas recursivas, criará muitos deles, mas eles não coexistirão ao mesmo tempo. Em cada chamada recursiva você cria uma matriz (ou 2 dependendo de uma implementação) para mesclar e eles ocupam não mais do que O (n) espaço, e então quando a mesclagem estiver pronto, esses arrays serão excluídos e alguns novos serão criados após um momento em alguma outra chamada recursiva. Se você contou quanto espaço todos os arrays que já foram criados ocuparam, seria O (n log n), mas você não precisa se preocupar com esta informação – você não precisa de mais do que espaço O (n), porque quando você precisa criar um array, todos os outros não existem mais e não ocupam qualquer memória . Observe que você pode simplesmente declarar 2 – ou 3 – arrays no início, cada um com o comprimento de n, e então armazenar a sequência em um deles, enquanto usa o outro para mesclar, isso melhorará o desempenho, bem como mostrará além dúvida, não há necessidade de mais do que O (n) de memória.
Resposta
Na classificação por mesclagem, quando estamos mesclando as 2 matrizes classificadas, criamos 2 matrizes temporárias. L [ ] = Arr [left, mid] (array da esquerda) para armazenar temporariamente o array antigo da esquerda para o meio (classificado pela metade esquerda) e R [] = Arr [mid + 1, right] (array da direita) para armazenar temporariamente o array antigo de mid + 1 para a direita (classificado pela metade direita), então mesclamos os dois array temporário no original. O fato de criarmos 2 array temporário para armazenar os números do array original, já que o array original tem n elementos, o temporário arrays são de tamanho n respectivamente e, portanto, o espaço extra de n e uma complexidade de espaço O (n). O espaço original do array não é levado em conta ao calcular a complexidade de espaço de uma espécie algoritmo de integração.