Algoritmos — Merge Sort
Neste artigo vou dar continuidade ao assunto de algoritmos, desta vez falando sobre o algoritmo de ordenação Merge Sort. Vamos lá!!!
Introdução
O Merge Sort é um algoritmo de ordenação que consiste em dividir uma estrutura em subconjuntos e ir aplicando a ordenação nos elementos que foram extraídos da estrutura originaria. Após a ordenação destes subconjuntos, é feita a mistura destes (merge) em um conjunto final ordenado. Podemos dizer literalmente que ele se utiliza daquela boa e velha frase da qual conhecemos: “Dividir e conquistar”.
Notação Big O
Quando comparado a outros algoritmos de ordenação, como por exemplo bubble-sort, insertion-sort e selection-sort, o Merge-Sort se mostra mais rápido e eficiente, isso quando se é utilizado uma grande quantidade de dados. Quando se é utilizado em pequenas quantidades de dados, não se mostra muito eficiente comparado com os outros algoritmos de ordenação.
Uma das desvantagens de se utilizar o Merge-Sort é o uso extra de memória, pois se é criada uma cópia do array a cada chamada recursiva da função de ordenação que implementa o Merge-Sort.
Acima está uma tabela de comparação com as notações Big O correlatas a cada tipo de algoritmo de ordenação.
Visual Go
Para ajudar no entendimento, há um site chamado visualgo, ele possui umas animações bem explicativas sobre alguns algoritmos de ordenação, vou deixar o link dele aqui também caso você queira consultar
Implementação
A classe MergeSort foi escrita em c#. Mantive a implementação utilizando recursos que toda linguagem disponibiliza, portanto acredito que seja fácil a compreensão.
Para entender melhor a implementação do algoritmo, sugiro que dê uma conferida no meu github.
Clone o repositório, execute, teste e entenda o seu funcionamento.
Conclusão
É sempre bom entender o funcionamento das coisas em sua essência. Algoritmos de ordenação nos acompanham no mundo do desenvolvimento de software. Podem não ser notados nitidamente em algum trecho de código de algum framework que utilizamos, mas garanto que “por debaixo dos panos” tem a implementação de algum deles.
Espero que tenha gostado e que tenha ajudado de alguma forma!!!
Até a próxima!!! o/
In God I Trust!!!
