algoritmo de ordenação

Algoritmo de ordenação: é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem -- em outras palavras, efetua sua ordenação completa ou parcial. As ordens mais usadas são a numérica e a lexicográfica.
Existem várias razões para se ordenar uma sequência. Uma delas é a possibilidade se acessar seus dados de modo mais eficiente.

Introdução ao MergeSort

História
Ainda existe uma discussão sobre o assunto, mas apareceram evidências de que o algoritmo foi proposto por John Von Neumann em 1945. Essa discussão existe, pois estudar as várias contribuições que ele fez é, ao mesmo tempo, complexa e fascinante. Essa complexidade devesse em parte a existência de muitas fontes de informação, algumas pouco acessíveis, outras discordantes entre si ou polêmicas.
A atribuição a ele veio de Knuth, que argumentou no seu livro ‘Arte de Programação Computacional: Ordenando e Procurando’ que Von Neumann foi o primeiro a descrever a idéia.

Significado do MergeSort
Nós vimos que o Quicksort é baseado em selecionar um elemento e dividir a lista em duas metades e então, ordenar-las separadamente. Há também um processo complementar o qual é chamado de junção. Dando 2 listas as quais estão ordenadas,combinando-as em uma lista ordenada maior.
O processo de Seleção e junção são complementares porque:
Seleção: divide a lista em 2 outras independentes.
Junção: une 2 listas independentes em uma lista maior ordenada. Isso insinua que o Mergesort consiste em duas chamadas recursivas e um processo de junção.
Então, Mergesort é um algoritmo recursivo, que é implementado dividindo uma sequência original em pares de dados, ordena-as e depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.
Assim, sua idéia básica é que é muito fácil criar uma sequência ordenada a partir de duas outras também ordenadas.
Classificação
- Ordenação por partição
O Mergesort é classificado como