O quê é o Merge Sort?
O Merge Sort (Ordenação por Mesclagem) é um algoritmo de ordenação por comparação criado por John von Neumann em 1945. O algoritmo funciona dividindo a coleção de elementos em duas sub-coleções, ordenando de forma recursiva cada sub-coleção e, em seguida, combinando as duas subcoleções.
Quando usar o Merge Sort?
- O Merge Sort pode ser usado para ordenar coleções grandes
- O Merge Sort pode ser usado quando uma ordenação estável é necessária.
Quais são as características do Merge Sort?
- O Merge Sort é um algoritmo de Divisão e Conquista.
- O Merge Sort é um algoritmo de ordenação por comparação.
- O Merge Sort é um algoritmo de ordenação estável.
- O Merge Sort pode ser usado para ordenar arranjos e listas.
- O desempenho do merge sort não depende da disposição dos dados na coleção de entrada.
Qual é o algoritmo do Merge Sort?
- Verifique se a coleção possui apenas um elemento. Em caso afirmativo, retorne.
- Divida a coleção em duas subcoleções.
- Ordene recursivamente cada subcoleção.
- Combine as duas subcoleções ordenadas em uma única.
- Retorne a coleção ordenada.
Qual é o desempenho do Merge Sort?
O desempenho do algoritmo Merge Sort não é impactado pela disposição dos dados no arranjo de entrada. Assim, o algoritmo apresenta tanto no pior caso quanto melhor caso um custo super-linear de comparações, em função do comprimento n do arranjo de entrada:
Como implementar o Merge Sort?
Veja o código completo no GitHub.