O merge total, ou ordenação por mistura é um exemplo de algoritmo de ordenação por intercalação.
O algoritmo consiste em dividir o problema em vários subproblemas e resolver esses subproblemas através da recursividade e após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas. Como o algoritmo Merge total usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.
Outra descrição, segundo Backes (2016, p. 36) "o algoritmo merge sort, também conhecido como ordenação por "intercalação", é um algoritmo recursivo que usa a ideia de dividir para conquistar para ordenar os dados de um array. O algoritmo merge sort divide, recursivamente, o array em duas partes, até que cada posição dele seja considerada um array de um único elemento. Em seguida, o algoritmo combina dois arrays de forma a obter um array maior e ordenado. Essa combinação dos arrays é feita intercalando seus elementos de acordo com o sentido da ordenação (crescente ou decrescente). O processo se repete até que exista apenas um array".
Podemos dividir o algoritmo em três passos:
Outra descrição, segundo Backes (2016, p. 36) "o algoritmo merge sort, também conhecido como ordenação por "intercalação", é um algoritmo recursivo que usa a ideia de dividir para conquistar para ordenar os dados de um array. O algoritmo merge sort divide, recursivamente, o array em duas partes, até que cada posição dele seja considerada um array de um único elemento. Em seguida, o algoritmo combina dois arrays de forma a obter um array maior e ordenado. Essa combinação dos arrays é feita intercalando seus elementos de acordo com o sentido da ordenação (crescente ou decrescente). O processo se repete até que exista apenas um array".
Podemos dividir o algoritmo em três passos:
- Dividir: Calcula o ponto médio do arranjo de dados (Complexidade O(k), ou seja, constante).
- Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2 (Complexidade O(N) – Linear).
- Combinar: Unir os sub - arranjos de dados em um único conjunto ordenado (Complexidade O(N) – Linear).
 |
| Figura 1 - Exemplo de ordenação completa de um array crescente. |
A Complexidade do algoritmo merge total é de O(N log N). Considerando N elementos, o tempo de execução do merge sort é sempre dessa ordem citada, porque ele cria uma cópia do array para cada chamada recursiva.
No pior caso, o merg sort realiza cerca de 39% menos comparações do que o quick sort faz no seu caso médio. Já no melhor caso, o merge sort realiza cerca de metade de do numero de iterações do seu pior caso.
A implementação comentada e o código estão disponíveis em: https://repl.it/@OsniMario/OverdueAnguishedIde
No pior caso, o merg sort realiza cerca de 39% menos comparações do que o quick sort faz no seu caso médio. Já no melhor caso, o merge sort realiza cerca de metade de do numero de iterações do seu pior caso.
A implementação comentada e o código estão disponíveis em: https://repl.it/@OsniMario/OverdueAnguishedIde
Também é possível implementar o Merge Sort utilizando apenas um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a O (n log n).
ResponderExcluirPara uma quantidade grande de dados o merge sort é mais rápido e eficiente que algoritmos mais simples, como o bubble sort e o selection sort. No entanto, para quantidades pequenas de dados, a situação se inverte e os algoritmos mais simples são mais eficientes. Além disso, vale salientar que o algoritmo foi desenvolvido por Von Neumann, responsável também por propor uma arquitetura de computadores que é utilizada até os dias atuais.
ResponderExcluirQuais as melhores formas de utilização do algoritmo? E em quais situações o algoritmo apresenta problemas?
ResponderExcluirComplementando sua postagem, o Merge Sort é útil para ordenar listas encadeadas em tempo O (nLogn). No caso de listas encadeadas, o caso é diferente principalmente devido à diferença na alocação de memória de matrizes e listas encadeadas. Ao contrário das matrizes, os nós da lista vinculada podem não estar adjacentes na memória. Ao contrário da matriz, na lista vinculada, podemos inserir itens no meio em O (1) espaço extra e O (1) tempo. Portanto, a operação de mesclagem da classificação de mesclagem pode ser implementada sem espaço extra para listas vinculadas.
ResponderExcluir