b) Considere que o algoritmo Merge Sort utiliza memória extra para os subarrays temporários em cada divisão. Qual seria a quantidade total de memória adicional utilizada durante a execução, em função de N?

Uma rede de farmácias possui diversas filiais, cada uma com sua própria base de dados de clientes. Para unificar esses dados, foi criada uma tabela chamada Clientes com N registros, possivelmente contendo clientes repetidos, pois o mesmo cliente pode visitar diferentes filiais. A rede deseja consolidar esses dados em uma tabela Clientes_Unicos, contendo apenas os clientes únicos.

Para isso, foi proposto o seguinte processo:
Etapa 1 – Ordenação dos dados:
A tabela Clientes será ordenada usando o algoritmo Merge Sort para facilitar a detecção de duplicatas.
 
Etapa 2 – Eliminação de duplicatas:
Após a ordenação, a tabela Clientes será percorrida. Cada cliente será comparado com o anterior, e apenas os clientes únicos serão copiados para a tabela Clientes_Unicos.

Essas etapas estão representadas no código a seguir:

 

Com base nas etapas descritas e no código, responda às seguintes perguntas:
a) Analise a complexidade computacional de cada etapa do processo (ordenar a tabela Clientes com Merge Sort e percorrer para eliminar duplicatas). Justifique sua resposta.
 
b) Considere que o algoritmo Merge Sort utiliza memória extra para os subarrays temporários em cada divisão. Qual seria a quantidade total de memória adicional utilizada durante a execução, em função de N? Explique o cálculo.
 
c) Explique como o algoritmo Merge Sort garante a estabilidade na ordenação. Por que essa propriedade é importante para resolver o problema descrito?