# Merge sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.
Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas).

## Características
### Algoritmo

Os três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:
* Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante $\Theta (1)$;
* Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com $2T(n/2)$ para o tempo de execução;
* Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo $\Theta (n)$
$T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}$

### Complexidade

* Complexidade de tempo: $\Theta (n\log _{2}n)$.
* Complexidade de espaço: $\Theta (n)$.

### Demonstração da complexidade de tempo

$T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}$
${\begin{array}{l}T(n)={2^{1}}.T\left({\frac {n}{2^{1}}}\right)+1.n\\T(n)={2^{1}}.\left({2.T\left({\frac {n}{2^{2}}}\right)+{\frac {n}{2}}}\right)+n={2^{2}}.T\left({\frac {n}{2^{2}}}\right)+2.n\\T(n)={2^{2}}.\left({2.T\left({\frac {n}{2^{3}}}\right)+{\frac {n}{4}}}\right)+2.n={2^{3}}.T\left({\frac {n}{2^{3}}}\right)+3.n\\\quad \vdots \\T(n)={2^{h-1}}.\left({2.T\left({\frac {n}{2^{h}}}\right)+{\frac {n}{2^{h-1}}}}\right)+h.n={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+h.n\end{array}}$
Para que $T(1)=T\left({\frac {n}{n}}\right)=\Theta (1)$ teremos que fazer com que ${2^{h}}=n\Rightarrow \lg {2^{h}}=\lg n\Rightarrow h=\lg n$
Então:
$T(n)={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+n.h=n.T\left({\frac {n}{n}}\right)+n.\lg n=n.T\left(1\right)+n.\lg n=n.\Theta (1)+n.\lg n=\Theta (n.\lg n)$

## Comparação com outros algoritmos de ordenação por comparação

Em comparação a outros algoritmos de divisão e conquista, como o 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, insertion e selection sort), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.
Abaixo uma tabela para comparação:
| Algoritmo | Tempo | Tempo | Tempo |
| | Melhor | Médio | Pior |
| Merge sort | $O(n\log _{2}n)$ | $O(n\log _{2}n)$ | $O(n\log _{2}n)$ |
| Quick sort | $O(n\log n)$ | $O(n\log n)$ | $O(n^{2})$ |
| Bubble sort | $O(n)$ | $O(n^{2})$ | $O(n^{2})$ |
| Insertion sort | $O(n)$ | $O(n^{2})$ | $O(n^{2})$ |
| Selection sort | $O(n^{2})$ | $O(n^{2})$ | $O(n^{2})$ |
A sua eficiência é a mesma para melhor, pior e caso médio, independentemente de como os dados do array estão organizados a ordenação será eficaz.
Obs.: O Bubble sort apresenta melhor caso como $O(n)$porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa $O(n)$. O Quick sort pode atingir um tempo de $O(n^{2})$em um caso específico quando o particionamento é desequilibrado.

## Observações

* É 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 $\Theta (n\log n)$.
* É um algoritmo estável na maioria das implementações, em que elas podem ser iterativas ou recursivas.
* É possível também implementar o algoritmo com espaço adicional $\Theta (1)$.
* Algoritmo Criado por Von Neumann em 1945.

### Desvantagens

* Utiliza funções recursivas;
* 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 $O(n\log n)$.

### Implementação em C++

Outra implementação em C++: