Revisão das 00h06min de 27 de junho de 2018 editar 186.226.220.242 (discussão) →‎Implementações do Mergesort: Melhora estética. Etiquetas: Edição via dispositivo móvel Edição feita através do sítio móvel ← Ver a alteração anterior		Revisão das 13h48min de 27 de junho de 2018 editar desfazer 45.226.16.34 (discussão) Correção da ortografia da palavra subproblemas Etiqueta: Editor Visual Ver a alteração posterior →
Linha 11: O '''''merge sort''''', ou [[Ordenação (computação)\|ordenação]] por mistura, é um exemplo de [[Ordenação por comparação\|algoritmo de ordenação por comparação]] do tipo [[Divisão e Conquista\|dividir-para-conquistar]]. Sua ideia básica consiste em Dividir (o problema em vários ~~sub-problemas~~subproblemas e resolver esses ~~sub-problemas~~subproblemas através da recursividade) e Conquistar (após todos os ~~sub-problemas~~subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos ~~sub-problemas~~subproblemas). Como o algoritmo ''Merge Sort'' usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas. == Características == Linha 17: 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 <math>\Theta(1)</math>; # Conquistar: [[Recursividade (ciência da computação)\|Recursivamente]] resolve dois ~~sub-problemas~~subproblemas, cada um de tamanho n/2, o que contribui com <math>2T(n/2)</math> para o tempo de execução; # Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo <math>\Theta(n)</math>.

Merge sort: diferenças entre revisões