Até aqui, no algorítimo Isertion-Sort usamos uma técnica de projeto de algorítimo chamada incremental, e provamos sua funcionalidade usando a técnica de invariante do laço. Para o algorítimo Merge-Sort usaremos uma técnica chamada de Divisão e Conquista. Esta técnica usa no geral, a recursividade, um método em que o algorítimo chama a si mesmo durante a solução de um problema. A divisão e conquista consiste em dividir o problema em instancias cada vez menores a ponto de ele se tornar bem simples. Após isso, o algorítimo recorre recursivamente a si mesmo pela solução destes pequenos problemas resultantes. No fim, ele combina as mini-soluções em uma solução grande para o problema original. A seguir, veja os três passos para a aplicação da técnica da divisão e conquista:
Dividir: o problema é dividido em subproblemas cada vez menores até se tornarem simples de resolver
Conquista: O algorítimo resolve o problema recursivamente, ou se o problema é pequeno o bastante, resolve direto.
Combinar: as soluções dos subproblemas são combinadas para formar a solução do problema original.
O algorítimo Merge-Sort segue à risca este paradigma. Ele Divide a sequencia a ser ordenada de n elementos em subsequências de n/2 cada, executando o passo da DIVISÃO. Depois segue ordenando as subsequencias recursivamente utilizando a intercalação, o que configura o passo da CONQUISTA. Por último o passo da COMBINAÇÃO que é conseguida intercalando as subsequências de forma a gerar a resposta ao problema original.
A recursividade deixa de existir quando a sequencia tiver cumprimento 1(ou seja, ordenada por si só). O passo mais importante no Merge-Sort é o da combinação onde recorremos ao processo MERGE(A,p,q,r) em que A é um arranjo e p,q,r são índices de enumeração onde p=<q<r partindo da premissa que A[p...q] e A[q+1...r] já estão ordenados. À partir disso, forma-se um único sub-arranjo ordenado que ficará no lugar de A[p...r]. Este procedimento leva um tempo teta(n) onde n= r-p+1.
No próximo post, o algoritmo MERGE. Até lá!
Algoritmos / Thomas H. Cormen... [et al.] ; [tradução Arlete Simille Marques]. - Rio de Janeiro : Elsevier, 2012. il.
Tradução de: Introduction to algorithms, 3rd ed.
Cap 2.
