Dada a sequência de números: 349258217462985 1, ordene-a em ordem não decrescente segundo os seguintes algoritmos, apresentando a sequência obtida após cada passo do algoritmo:
MergeSort
MergeSort
Passo 1
Resumo do enunciado: temos a sequência de 16 números 3, 4, 9, 2, 5, 8, 2, 1, 7, 4, 6, 2, 9, 8, 5, 1 e queremos ordená-la em ordem não decrescente usando o algoritmo MergeSort (divisão e conquista). Precisaremos dividir a lista em sublistas, ordenar cada sublista trivialmente e depois mesclar (merge) pares de sublistas ordenadas, aumentando gradualmente o tamanho dos blocos.
Passo 2
Sequência inicial:
Passo 3
Na primeira fase (tamanho de bloco = 1), cada par de elementos é mesclado de forma ordenada. Mesclamos (3,4), (9,2), (5,8), (2,1), (7,4), (6,2), (9,8) e (5,1). O resultado é:
Passo 4
Na segunda fase (tamanho de bloco = 2), mesclamos pares de blocos de 2 elementos: (3,4)&(2,9), (5,8)&(1,2), (4,7)&(2,6), (8,9)&(1,5). O resultado é:
Passo 5
Na terceira fase (tamanho de bloco = 4), mesclamos pares de blocos de 4 elementos: (2,3,4,9)&(1,2,5,8) e (2,4,6,7)&(1,5,8,9). O resultado é:
Passo 6
Na quarta fase (tamanho de bloco = 8), mesclamos os dois blocos de 8 elementos: (1,2,2,3,4,5,8,9)&(1,2,4,5,6,7,8,9). O resultado final é: