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

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:
3,;4,;9,;2,;5,;8,;2,;1,;7,;4,;6,;2,;9,;8,;5,;1

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 é:
3,;4,;2,;9,;5,;8,;1,;2,;4,;7,;2,;6,;8,;9,;1,;5

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 é:
2,;3,;4,;9,;1,;2,;5,;8,;2,;4,;6,;7,;1,;5,;8,;9

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 é:
1,;2,;2,;3,;4,;5,;8,;9,;1,;2,;4,;5,;6,;7,;8,;9

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 é:
1,;1,;2,;2,;2,;3,;4,;4,;5,;5,;6,;7,;8,;8,;9,;9

Resposta

1,;1,;2,;2,;2,;3,;4,;4,;5,;5,;6,;7,;8,;8,;9,;9

Exercícios relacionados