Ordenação por Intercalação

Edição de 21h45min de 28 de novembro de 2008

Ordenação por intercalação (Merge Sort) é um algoritmo de ordenação muito utilizado em computação, criado pelo matemático húngaro John von Neumann (1903-1957).

Princípio de Funcionamento:

O princípio básico de funcionamento do Merge Sort é simples e intuitivo: o algoritmo divide a lista a ser ordenada em várias sublistas, sempre em duas partes, até que as listas restantes contenham apenas um elemento. Após esta divisão o algoritmo faz o caminho inverso, ou seja, ele começa a "remontar" o vetor, porém ordenando os elementos (que estão em menor número) enquanto o os vetores maiores são recriados.

Características:

- O Merge Sort necessita de um vetor auxiliar para funcionar, de tamanho igual ao do vetor a ser ordenado, o que constitui uma desvantagem deste algoritmo.

- Sua complexidade é n<math>log[2]</math>n, sendo n o número de elementos que serão ordenados.

- O Merge Sort é considerado como o melhor algoritmo de ordenação já inventado, devido à sua simplicidade e eficiência.

Exemplo

Segue abaixo um exemplo de aplicação do Merge Sort para ordenar um vetor de 8 elementos:

15 99 52 14 50 64 20 77

Divisão em duas partes:

15 99 52 14 - 50 64 20 77

Divisão da primeira parte em duas outras partes:

15 99 - 52 14

Análise do primeiro par:

15- 99

Como 15 é menor do que 99, a ordem é mantida.

Análise do segundo par:

52 -14

Como 52 é maior do que 14, a ordem é invertida:

14 -52

Agora restam dois pares ordenados:

15 99 - 14 52

O algoritmo agora compara o menor valor de cada um dos dois vetores:

15 -14

Como 14 é menor do que 15, esse valor será o primeiro da lista de 4 elementos:

14 X X X

Compara-se 15 com o outro elemento do segundo vetor. Como 15 é menor do que 52, 15 ocupará segunda posição:

14 15 X X

Agora simplesmente compara-se os dois elementos restantes. 99 é maior do que 52, logo 52 ocupará a terceira posição, e 99 a quarta posição neste vetor de 4 elementos:

14 15 52 99

O processo é repetido de forma idêntica para a outra primeira metade do vetor inicial, que apresentará a seguinte configuração:

20 50 64 77

Neste ponto tem-se dois vetores ordenados:

14 15 52 99 - 20 50 64 77

O próximo e último passo é fazer a fusão destes dois vetores, de forma similar àquela já feita, comparando o menor elemento de cada um dos dois vetores e posicionando o menor elemento ordenadamente na lista original.

Feito este processo, o resultado final será:

14 15 20 50 52 64 77 99