Merge sort: diferenças entre revisões

* Complexidade de tempo: <math>\Theta(n \log n)</math>.

Em comparação a outros algoritmos de divisão e conquista, como o Quick sort[[Quicksort]], o Merge apresenta a mesma complexidade. Já em comparação a algoritmos mais básicos de ordenação por comparação e troca ([[Bubble sort|bubble]], [[Insertion sort|insertion]] e [[selection sort]]), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados<ref>{{citar web|url=https://www.blogcyberini.com/2018/07/merge-sort.html|titulo=Merge Sort|data=1 de julho 2018|acessodata=6 de julho de 2018|publicado=Blog Cyberini|ultimo=Felipe|primeiro=Henrique}}</ref>. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.

|<math>O(n*\log( n))</math>

|<math>O(n*\log( n))</math>

|<math>O(n*\log( n))</math>

|<math>O(n*\log( n))</math>

|<math>O(n*\log( n))</math>

|<math>O(n<sup>^2)</supmath>)

|<math>O(n)</math>

|<math>O(n<sup>^2)</supmath>)

|<math>O(n<sup>^2)</supmath>)

|<math>O(n)</math>

|<math>O(n<sup>^2)</supmath>)

|<math>O(n<sup>^2)</supmath>)

|<math>O(n<sup>^2)</supmath>)

|<math>O(n<sup>^2)</supmath>)

|<math>O(n<sup>^2)</supmath>)

Obs.: O [[Bubble sort]] apresenta melhor caso como <math>O(n) </math>porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa <math>O(n)</math><ref>{{citar web|url=https://www.blogcyberini.com/2018/02/bubble-sort.html|titulo=Bubble Sort|data=19 de fevereiro de 2018|acessodata=6 de julho de 2018|publicado=Blog Cyberini|ultimo=Felipe|primeiro=Henrique}}</ref>. O [[Quicksort|Quick sort]] pode atingir um tempo de <math>O(n<sup>2)</supmath>) em um caso específico quando o particionamento é desequilibrado.

* É possível implementar o ''merge sort'' utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a <math>\Theta(n \log n)</math>.

* Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a <math>O(n \log n)</math>.

* {{Link|en|2=http://c2.com/cgi/wiki?MergeSort |3=Merge Sort}}