relatorio

MERGE SORT

Imperatriz
2014

Imperatriz
2014
SUMÁRIO

P
1 Ordenação 4
1.1 ALGORITMO DE ORDENAÇÃO 4
2 Histórico 4
3 Merge sort 4
4 PERFOMANCE 5
5 ANALISE DO ALGORITMO 5
6 VANTAGENS 5
7 DESVANTAGENS 5
8 CONCLUSÃO 6

1 Ordenação

É o ato de colocar um conjunto de dados em uma determinada ordem predefinida, permitindo o acesso mais eficiente aos dados. O termo técnico em inglês para ordenação é sorting, cuja tradução literal é "classificação". Algumas ordens são facilmente definidas. Por exemplo, ordenação ascendente e descendente.
Contudo, existem ordens, especialmente de dados compostos, que podem ser não triviais de se estabelecer.

1.1 ALGORITMO DE ORDENAÇÃO

É o algoritmo que coloca os elementos do conjunto de dados abordados em ordem mediante os critérios predefinidos.

2 Histórico

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.

3 Merge sort

Tal algoritmo também é conhecido como ordenação por mistura ou intercalação de elementos. Sua idéia básica é ‘Dividir e Conquistar’, ou seja, divide o conjunto de dados a ser ordenado, de forma recursiva, em subconjuntos até que tenha apenas um elemento em cada subgrupo, após essa etapa ocorre à combinação de dois subconjuntos de formar a obter um