Algoritmo de ordenação Merge Sort

Trecho de código do algoritmo Merge Sort

A ordenação de elementos costuma ser uma das operações mais adotadas pelos desenvolvedores nos seus softwares. Geralmente, os usuários dos sistemas exigem que um determinado output possa ser classificado, ou até mesmo que o resultado em questão seja ordenado por padrão.

Em boa parte das ocasiões, os programadores implementam tal funcionalidade no lado do banco de dados. Isso significa que a ordenação acaba sendo direcionada para a consulta SQL ou NoSQL. Entretanto, há situações nas quais a classificação dos registros deve ser processada diretamente no back-end, de modo que o servidor do banco de dados não fique sobrecarregado.

Quando o cenário descrito no parágrafo anterior se encaixa em algum caso de uso da aplicação, o desenvolvedor passa a ter que pensar sobre os algoritmos de ordenação. Assim como os algoritmos de busca, o catálogo dessa família de algoritmos é recheado de opções que variam em complexidade e outras características relevantes.

O Merge Sort, ou Ordenação por Mesclagem, tem um lugar de destaque na lista dos algoritmos de classificação. Conforme explicado nos próximos tópicos do artigo, esse algoritmo apresenta um desempenho notável para inputs de grandeza superior. Logo, quem domina os conceitos por trás do Merge Sort dispõe de um recurso poderoso que ordena inúmeras estruturas de dados.

Entendendo o algoritmo

Diferente dos algoritmos básicos de ordenação, a exemplo do Bubble Sort, o Merge Sort requer uma maior curva de aprendizagem. Além disso, a sua codificação também foge da trivialidade, sendo fundamental compreender em um primeiro momento a lógica que serve de base para o algoritmo.

No que tange a categorização do Merge Sort, ele figura no rol dos algoritmos de dividir para conquistar. Ou seja, a estratégia do algoritmo consiste na divisão recursiva do vetor de input em fragmentos menores, de tal forma que a ordenação da estrutura ocorra de uma maneira simplificada.

Execução do algoritmo Merge Sort

A imagem animada acima ilustra o passo a passo da execução do Merge Sort. Olhando com atenção, nitidamente o algoritmo repete um conjunto de instruções para classificar o array em sua totalidade.

• Recursivamente, o algoritmo divide o vetor pela metade, até que reste apenas um elemento.
• Uma vez que o vetor atinge um estado indivísivel, o algoritmo inicia o processo de mesclagem em cada parte fracionada. 
• Durante a rotina de mesclagem, o algoritmo usa dois vetores auxiliares. O primeiro deles recebe os itens do segmento dividido à esquerda (arr1), enquanto o segundo recebe os itens do segmento dividido à direita (arr2).
• Ainda no procedimento de mesclagem, os vetores auxiliares são percorridos simultaneamente. Iteração a iteração, o algoritmo escolhe o menor dos elementos atuais em arr1 e arr2, e copia este item para a próxima posição do vetor original. Com isso, a mesclagem ordena a estrutura por completo.

Analisando a implementação do algoritmo

Comparado a outros algoritmos populares de ordenação, o Merge Sort possui uma vantagem competitiva. A sua complexidade de tempo é classificada em Θ(nLogn), patamar que transcende à complexidade quadrática de Bubble Sort, Selection Sort e Insertion Sort. Vale frisar que os detalhes pertinentes à performance do Merge Sort estão pormenorizados na seção subsequente do post.

A técnica de Divide and Conquer viabiliza que a ordenação dos vetores seja realizada em pouquíssimo tempo, dado que o algoritmo inspeciona os elementos do input menos vezes no decorrer da sua execução. E, justamente por dividir o array até o limite, o Merge Sort ordena blocos menores da estrutura, reduzindo assim a quantidade de varreduras necessárias.

1. A função verifica se a variável esquerda, que representa o índice delimitador da metade à esquerda do vetor arr, é superada pela variável direita, a qual simboliza o índice delimitador da metade à direita do vetor arr. Na primeira execução, o valor de esquerda estará atribuído como zero (primeiro índice de arr), à medida que o valor de direita estará atribuído como n - 1, sendo que n reflete a quantidade de elementos em arr.
2. A variável metade recebe o valor do índice de arr que corresponde exatamente à posição central do vetor em processo de ordenação. Dessa forma, a rotina inicia a divisão da estrutura, seguindo os fundamentos da metodologia Divide and Conquer.
3. A partir de então, o algoritmo executa chamadas recursivas, considerando somente o segmento à esquerda do vetor arr. Até que não seja mais possível dividir o vetor em duas partes, esta primeira recursão de MergeSort continua empilhando execuções.
4. No instante que arr se torna irredutível, a função aciona outra chamada recursiva, desta vez considerando somente o segmento à direita do vetor. Novamente, MergeSort repete essa recursão até o limite da segunda metade ser atingido.
5. Após a divisão tanto à esquerda quanto à direita do vetor alcançar o seu estágio final, o procedimento Merge reúne estas duas metades para ordená-las na estrutura original de arr.
6. Dentro da função Merge, os vetores auxiliares arrEsquerda e arrDireita são declarados com o objetivo de armazenar os elementos das metades à esquerda e à direita de arr, respectivamente. Os dois laços de repetição for se encarregam de popular os arrays. 
7. A variável de controle k tem o seu valor atribuído com base na variável esquerda. Na prática, k estabelece o índice de partida para a ordenação do vetor arr no método Merge.
8. O loop while ordena os elementos do vetor arr. Para isso, a cada iteração, duas condições são testadas. A primeira delas verifica se o item de arrDireita supera ou iguala o item de arrEsquerda. Nesse caso, o vetor arr recebe o item do vetor auxiliar arrEsquerda, e o índice i é incrementado em um para que o próximo elemento de arrEsquerda seja inspecionado. Porém, se o item de arrDireita for menor, o vetor arr recebe o elemento do vetor auxiliar arrDireita, e o índice j é incrementado em um para que o próximo item de arrDireita seja inspecionado.
9. Como o primeiro loop while itera simultaneamente por arrEsquerda e arrDireita, existe a possibilidade de que elementos remanescentes permaneçam em um destes vetores auxiliares. Tendo isso em vista, a função Merge encerra a sua execução com mais dois loops while, que validam se um ou mais itens de arrEsquerda ou arrDireita devem ser atribuídos para completar a ordenação do vetor original arr.

Comparando o desempenho do algoritmo com o Bubble Sort

Merge Sort vasculha o vetor de input inúmeras vezes até concluir a sua ordenação. A passagem inicial pela estrutura mescla apenas um elemento, enquanto a segunda passagem mescla dois elementos e a iésima passagem mescla blocos de tamanho 2i-1. Em termos matemáticos, o total aproximado de passagens que Merge Sort faz no input é de log2n.

Já no que diz respeito a rotina de mesclagem, o algoritmo une e classifica dois segmentos em tempo linear. Portanto, juntando as principais operações do algoritmo, a sua complexidade de tempo está no nível de Θ(nLogn).

Método	Input	Média de tempo	Espaço alocado
MétodoMergeSort	InputInt32[10]	Média de tempo250.56 ns	Espaço alocado624 B
MétodoBubbleSort	InputInt32[10]	Média de tempo47.86 ns	Espaço alocado-
MétodoMergeSort	InputInt32[100]	Média de tempo3,510.93 ns	Espaço alocado8000 B
MétodoBubbleSort	InputInt32[100]	Média de tempo4,841.24 ns	Espaço alocado-
MétodoMergeSort	InputInt32[1000]	Média de tempo44,197.05 ns	Espaço alocado92304 B
MétodoBubbleSort	InputInt32[1000]	Média de tempo465,293.47 ns	Espaço alocado-
MétodoMergeSort	InputInt32[10000]	Média de tempo720,451.90 ns	Espaço alocado1072017 B
MétodoBubbleSort	InputInt32[10000]	Média de tempo45,510,431.55 ns	Espaço alocado55 B
MétodoMergeSort	InputInt32[100000]	Média de tempo8,232,976.55 ns	Espaço alocado12031272 B
MétodoBubbleSort	InputInt32[100000]	Média de tempo5,411,927,633.33 ns	Espaço alocado600 B

Por outro lado, Bubble Sort possui uma complexidade quadrática de tempo. No frigir dos ovos, isso quer dizer que Merge Sort ostenta um desempenho superior, sobretudo para inputs maiores. Basta observar a tabela acima, que comprova essa última afirmação.

Analisando cuidadosamente, Bubble Sort executou com mais agilidade somente no cenário de ordenação de dez elementos. Considerando cem, mil, dez mil e cem mil itens no vetor de input, o algoritmo Merge Sort apresentou ganhos incríveis de 1.3x, 10.5x, 63.1x e 657.3x, respectivamente.

Enfim, o trade-off do Merge Sort reside no consumo do espaço auxiliar de memória. Graças à recursividade, o algoritmo empilha diversas chamadas da sua função, fato que impacta no uso da memória do programa. Assim sendo, Merge Sort requer um espaço adicional linear, o qual cresce de acordo com a quantidade de elementos do vetor ordenado.

O código-fonte completo dos algoritmos e os detalhes extras acerca do desempenho de cada um deles estão disponíveis no meu repositório do Github.