merg sort

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.
Sua idéia básica consiste em Dividir(o problema em vários sub-problemas e resolver esses sub-problemas através da recursividade) e Conquistar(após todos os sub-problemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos sub-problemas).Como o algoritmo do Merge Sort usa a recursividade em alguns problemas esta técnica não é muito eficiente devido ao alto consumo de memória e tempo de execução.
Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:
1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.
Características
Complexidade de tempo: Θ(n log2 n)
Complexidade de espaço: Θ(n)
[editar] Observações

Exemplo de execução do merge sort.
É 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 Θ(n log n).
É possível também implementar o algoritmo com espaço adicional Θ(1)
Algoritmo Criado por Von Neumann em 1945.
[editar] Desvantagens
Implementação complexa
Ideia complexa
Utiliza funções recursivas
3 Merge Sort
3.1 Algoritmo
Criado em 1945 pelo matematico americano John Von Neumann o Merge Sort ´e outro exemplo de um algoritmo de ordenacao que faz uso da estrat´egia “dividir para conquistar” para resolver problemas.
O Merge Sort parte dos seguintes princ´ıpios para solucionar o problema de ordena¸c˜ao:
• Menos passos s˜ao necess´arios para ordenar uma lista menor.
• ´E mais f´acil construir uma lista ordenada a partir de duas listas j´a ordenadas a de duas n˜ao ordenadas.
Logo, ele pode ser conceitualmente descrito nos seguintes passos:
1. Verifica se n˜ao ´e um caso base: lista