O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação por comparação do tipo dividir-para-conquistar.
Sua ideia básica consiste em Dividir (o problema em vários subproblemas e resolver esses subproblemas através da recursividade) e Conquistar (após todos os subproblemas terem sido resolvidos ocorre a conquista que é a união das resoluções dos subproblemas).
Características Algoritmo Os três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são: Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante ; Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com para o tempo de execução; Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo miniaturadaimagem|500x500px|Árvore de recursão
Complexidade Complexidade de tempo: . Complexidade de espaço: .
Demonstração da complexidade de tempo
Para que teremos que fazer com que
Então:
Comparação com outros algoritmos de ordenação por comparação Em comparação a outros algoritmos de divisão e conquista, como o Quicksort, o Merge apresenta a mesma complexidade. Já em comparação a algoritmos mais básicos de ordenação por comparação e troca (bubble, insertion e selection sort), o Merge é mais rápido e eficiente quando é utilizado sobre uma grande quantidade de dados. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.
Abaixo uma tabela para comparação: AlgoritmoTempoMelhorMédioPiorMerge sortQuick sortBubble sortInsertion sortSelection sort A sua eficiência é a mesma para melhor, pior e caso médio, independentemente de como os dados do array estão organizados a ordenação será eficaz.
Obs.: O Bubble sort apresenta melhor caso como porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa . O Quick sort pode atingir um tempo de em um caso específico quando o particionamento é desequilibrado.
Observações thumb|Exemplo de execução do merge sort.
É possível implementar o merge sort utilizando somente um vetor auxiliar ao longo de toda a execução, tornando assim a complexidade de espaço adicional igual a . É um algoritmo estável na maioria das implementações, em que elas podem ser iterativas ou recursivas. É possível também implementar o algoritmo com espaço adicional . Algoritmo Criado por Von Neumann em 1945.
Desvantagens Utiliza funções recursivas; Gasto extra de memória. O algoritmo cria uma cópia do vetor para cada nível da chamada recursiva, totalizando um uso adicional de memória igual a .
Implementações do Mergesort Pseudocódigo função mergesort (vetor a) se (n == 1) retornar a
vetor l1 = a ... a[n/2] vetor l2 = a[n/2 + 1] ... a[n]
l1 = mergesort(l1) l2 = mergesort(l2)
retornar mesclar(l1, l2) fim da função mergesort
função mesclar (vetor a, vetor b) vetor c
enquanto (a e b têm elementos) if (a > b) adicionar b ao final de c remover b de b senão adicionar a ao final de c remover a de a enquanto (a tem elementos) adicionar a ao final de c remover a de a enquanto (b tem elementos) adicionar b ao final de c remover b de b retornar c fim da função mesclar
Código em C void merge(int vetor[], int comeco, int meio, int fim) { int com1 = comeco, com2 = meio+1, comAux = 0, tam = fim-comeco+1; int *vetAux; vetAux = (int*)malloc(tam * sizeof(int));
while(com1 <= meio && com2 <= fim){ if(vetor[com1] < vetor[com2]) { vetAux[comAux] = vetor[com1]; com1++; } else { vetAux[comAux] = vetor[com2]; com2++;
comAux++;
while(com1 <= meio){ //Caso ainda haja elementos na primeira metade vetAux[comAux] = vetor[com1]; comAux++; com1++;
while(com2 <= fim) { //Caso ainda haja elementos na segunda metade vetAux[comAux] = vetor[com2]; comAux++; com2++;
for(comAux = comeco; comAux <= fim; comAux++){ //Move os elementos de volta para o vetor original vetor[comAux] = vetAux[comAux-comeco];
free(vetAux); }
void mergeSort(int vetor[], int comeco, int fim){ if (comeco < fim) { int meio = (fim+comeco)/2;
mergeSort(vetor, comeco, meio); mergeSort(vetor, meio+1, fim); merge(vetor, comeco, meio, fim);
Implementação em C++ void merge(int *saida, int *auxiliar, int inicio, int meio, int fim){ int i, j, k; i = inicio; j = meio + 1; k = inicio; while(i <= meio && j <= fim){ if(auxiliar[i] < auxiliar[j]){ saida[k] = auxiliar[i]; i++;
else{ saida[k] = auxiliar[j]; j++;
k++;
while(i <= meio){ saida[k] = auxiliar[i]; i++; k++;
while(j <= fim){ saida[k] = auxiliar[j]; j++; k++;
//Copia os elementos que foram ordenados para o auxiliar for(int p = inicio; p <= fim; p++) auxiliar[p] = saida [p]; }
void mergeSort(int *saida, int *auxiliar, int inicio, int fim){ if(inicio < fim){ int meio = (inicio + fim) / 2; mergeSort(saida, auxiliar, inicio, meio); mergeSort(saida, auxiliar, meio + 1, fim); merge(saida, auxiliar, inicio, meio, fim);
}Outra implementação em C++:void Juntar(int vetor[], int ini, int meio, int fim, int vetAux[]) { int esq = ini; int dir = meio; for (int i = ini; i < fim; ++i) { if ((esq < meio) and ((dir >= fim) or (vetor[esq] < vetor[dir]))) { vetAux[i] = vetor[esq]; ++esq;
else { vetAux[i] = vetor[dir]; ++dir;
//copiando o vetor de volta for (int i = ini; i < fim; ++i) { vetor[i] = vetAux[i];
void MergeSort(int vetor[], int inicio, int fim, int vetorAux[]) { if ((fim - inicio) < 2) return;
int meio = ((inicio + fim)/2); MergeSort(vetor, inicio, meio, vetorAux); MergeSort(vetor, meio, fim, vetorAux); Juntar(vetor, inicio, meio, fim, vetorAux); }
void MergeSort(int vetor[], int tamanho) { //função que o usuario realmente chama //criando vetor auxiliar int vetorAux[tamanho]; MergeSort(vetor, 0, tamanho, vetorAux); }
Código em Java public class WikiMerge<T extends Comparable<T>>{ /** * Método que recebe um array de inteiros e dois inteiros referentes ao início e ao fim * da ordenação desse array, o que nos garante o poder de escolher uma faixa do array * para ser ordenado. * * @param array * @param indiceInicio * @param indiceFim */ public void ordena(T[] array, int indiceInicio, int indiceFim) {
// Condicional que verifica a validade dos parâmetros passados. if (array != null && indiceInicio < indiceFim && indiceInicio >= 0 && indiceFim < array.length && array.length != 0) { int meio = ((indiceFim + indiceInicio) / 2);
ordena(array, indiceInicio, meio); ordena(array, meio + 1, indiceFim);
merge(array, indiceInicio, meio, indiceFim);
/** * O merge consiste na junção de duas listas já ordenadas. * Usa um array auxiliar. * * @param array * @param indiceInicio * @param meio * @param indiceFim */ public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {
T[] auxiliar =(T[]) new Comparable[array.length]; //Copiando o trecho da lista que vai ser ordenada for (int i = indiceInicio; i <= indiceFim; i++) { auxiliar[i] = array[i];
//Índices auxiliares int i = indiceInicio; int j = meio + 1; int k = indiceInicio;
//Junção das listas ordenadas while (i <= meio && j <= indiceFim) { if (auxiliar[i].compareTo(auxiliar[j]) < 0) { array[k] = auxiliar[i]; i++; } else { array[k] = auxiliar[j]; j++;
k++;
//Append de itens que não foram usados na Junção while (i <= meio) { array[k] = auxiliar[i]; i++; k++;
//Append de itens que não foram usados na Junção while (j <= indiceFim) { array[k] = auxiliar[j]; j++; k++;
//teste
Código em Python def mergeSort(lista):
if len(lista) > 1:
meio = len(lista)//2 #também é valido: meio = int(len(lista)/2)
listaDaEsquerda = lista[:meio] listaDaDireita = lista[meio:]
mergeSort(listaDaEsquerda) mergeSort(listaDaDireita)
i = 0 j = 0 k = 0
while i < len(listaDaEsquerda) and j < len(listaDaDireita):
if listaDaEsquerda[i] < listaDaDireita[j]: lista[k]=listaDaEsquerda[i] i += 1 else: lista[k]=listaDaDireita[j] j += 1 k += 1
while i < len(listaDaEsquerda):
lista[k]=listaDaEsquerda[i] i += 1 k += 1
while j < len(listaDaDireita): lista[k]=listaDaDireita[j] j += 1 k += 1 return lista
Ver também Ordenação de vector Quick sort Bubble sort Selection sort TwistSort Pesquisa binária sort-merge utility Heapsort Shell sort Radix sort
Ligações externas
Merge sort em 13 linguagens Merge Sort paralelo em Java (multithreading)
Categoria:Algoritmos de ordenação
no:Sorteringsalgoritme#Flettesortering