Vimos que o número total de elementos a serem intercalados neste passo é r-p+1 e que este também é o tempo levado pelo procedimento MERGE. agora o algorítimo sugerido a seguir faz este procedimento de organizar de forma crescente os subconjuntos de cartas que já estão ordenadas.
MERGE(A, p, q, r)
1 n1= q - p + 1
2 n2= r - q
3 sejam L[1..n1 + 1] e R[1.. n2 + 1] novos arranjos
4 for i = 1 to n1
5 L[i] = A[p + i - 1]
6 for j = 1 to n2
7 R[j] = A[q + j]
8 L[n1 + 1] = z
9 R[n2 + 1] = z
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 then A[k] = L[i]
15 i = i + 1
16 else A[k] = R[j]
17 j = j + 1
O algorítimo acima funciona assim: linhas 1 e 2 calculam as extensões dos subarranjos a serem organizados. A linha 3 cria mais dois Arranjos que recebem os L e R. Na linha 4 e 5 copia o Arranjo A[ p .. q] em L[1 .. n1] e as 6 e 7 faz o mesmo para A[ q + 1 .. r] em R[1 .. n2]. As linhas 8 e 9 possuem uma nuance interessante. Aplica-se aqui uma carta de nome z que é um marcador indicando uma carta de valor infinito que já não precisa ser ordenada. Estas cartas são colocadas nas extremidades dos arranjos L e R. De 10 a 17 os r - p + 1 passos básicos são executados.
No próximo post vamos fazer a análise da corretude deste algorítimo e depois implementar o MERGE-SORT de fato, introduzindo a recursividade. 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.
