Recursividade - Parte 2 ou MergeSort

O merge sort é um algoritmo de ordenação que utiliza recursividade em uma estratégia do tipo dividir-para-conquistar que consiste em

• Dividir: o conjunto de dados em vários subconjuntos e ordenar esses subconjuntos através da recursividade, isto é, por divisão sucessiva até que o problema fique simples (veja no vídeo)
• Conquistar: após todos os subconjuntos terem sido ordenados ocorre a união das resoluções em um subconjunto maior até que tenhamos todos o conjunto original ordenado.

No vídeo fica claro que a execução é feita em 3 passos:

1. Dividir os dados em subconjuntos pequenos;
2. Classificar as duas metades recursivamente aplicando o merge sort;
3. Juntar as duas metades em um único conjunto já ordenado.

Como este algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução. As principais recomendações para tornar este algoritmo mais eficiente são:

• como o merge sort não é muito eficiente para pequenos conjuntos, devemos utilizar um outro método para subconjuntos com 10 ou menos elementos
• verificar se o conjunto de dados já está ordenado
• reduzir o tempo de ordenação eliminando a necessidade de cópia para a estrutura de dados auxiliar.

Vamos ver a nossa classe:

Você vai encontrar diversas informações úteis sobre este algoritmo no site do prof Sedgewick.