Merge sort – Wikipédia, a enciclopédia livre

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (notícias • livros • acadêmico)). (Junho de 2022)

Merge sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	${\displaystyle \Theta (n\log n)}$
complexidade caso médio	${\displaystyle \Theta (n\log n)}$
complexidade melhor caso	${\displaystyle \Theta (n\log n)}$ típico, ${\displaystyle \Theta (n)}$ variante natural
complexidade de espaços pior caso	${\displaystyle \Theta (n\log n)}$
Algoritmos
Esta caixa: ver discutir

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).

Os três passos úteis dos algoritmos de divisão e conquista, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Calcula o ponto médio do sub-arranjo, o que demora um tempo constante ${\displaystyle \Theta (1)}$;
2. Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com ${\displaystyle 2T(n/2)}$ para o tempo de execução;
3. Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo ${\displaystyle \Theta (n)}$

${\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}$

• Complexidade de tempo: ${\displaystyle \Theta (n\log _{2}n)}$.
• Complexidade de espaço: ${\displaystyle \Theta (n)}$.

${\displaystyle T(n)={\begin{cases}\Theta (1),&{\text{se }}n{\text{ = 1}}\\2T(n/2)+\Theta (n),&{\text{se }}n>{\text{ 1}}\end{cases}}}$

${\displaystyle {\begin{array}{l}T(n)={2^{1}}.T\left({\frac {n}{2^{1}}}\right)+1.n\\T(n)={2^{1}}.\left({2.T\left({\frac {n}{2^{2}}}\right)+{\frac {n}{2}}}\right)+n={2^{2}}.T\left({\frac {n}{2^{2}}}\right)+2.n\\T(n)={2^{2}}.\left({2.T\left({\frac {n}{2^{3}}}\right)+{\frac {n}{4}}}\right)+2.n={2^{3}}.T\left({\frac {n}{2^{3}}}\right)+3.n\\\quad \vdots \\T(n)={2^{h-1}}.\left({2.T\left({\frac {n}{2^{h}}}\right)+{\frac {n}{2^{h-1}}}}\right)+h.n={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+h.n\end{array}}}$

Para que ${\displaystyle T(1)=T\left({\frac {n}{n}}\right)=\Theta (1)}$ teremos que fazer com que ${\displaystyle {2^{h}}=n\Rightarrow \lg {2^{h}}=\lg n\Rightarrow h=\lg n}$

Então:

${\displaystyle T(n)={2^{h}}.T\left({\frac {n}{2^{h}}}\right)+n.h=n.T\left({\frac {n}{n}}\right)+n.\lg n=n.T\left(1\right)+n.\lg n=n.\Theta (1)+n.\lg n=\Theta (n.\lg n)}$

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^[1]. Para entradas pequenas os algoritmos de ordenação por comparação mais básicos são pró-eficientes.

Abaixo uma tabela para comparação^[2]:

Algoritmo	Tempo
	Melhor	Médio	Pior
Merge sort	${\displaystyle O(n\log _{2}n)}$	${\displaystyle O(n\log _{2}n)}$	${\displaystyle O(n\log _{2}n)}$
Quick sort	${\displaystyle O(n\log n)}$	${\displaystyle O(n\log n)}$	${\displaystyle O(n^{2})}$
Bubble sort	${\displaystyle O(n)}$	${\displaystyle O(n^{2})}$	${\displaystyle O(n^{2})}$
Insertion sort	${\displaystyle O(n)}$	${\displaystyle O(n^{2})}$	${\displaystyle O(n^{2})}$
Selection sort	${\displaystyle O(n^{2})}$	${\displaystyle O(n^{2})}$	${\displaystyle O(n^{2})}$

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 ${\displaystyle O(n)}$porque o algoritmo pode ser modificado de forma que, se a lista já estiver ordenada, basta apenas uma verificação básica que custa ${\displaystyle O(n)}$^[3]. O Quick sort pode atingir um tempo de ${\displaystyle O(n^{2})}$em um caso específico quando o particionamento é desequilibrado.

• É 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 ${\displaystyle \Theta (n\log n)}$.
• É 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 ${\displaystyle \Theta (1)}$.
• Algoritmo Criado por Von Neumann em 1945.

• 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 ${\displaystyle O(n\log n)}$.

função mergesort (vetor a)      se (n == 1) retornar a       vetor l1 = a[0] ... 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[0] > b[0])                adicionar b[0] ao final de c                remover b[0] de b           senão                adicionar a[0] ao final de c                remover a[0] de a      enquanto (a tem elementos)           adicionar a[0] ao final de c           remover a[0] de a      enquanto (b tem elementos)           adicionar b[0] ao final de c           remover b[0] de b      retornar c fim da função mesclar

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);     } } 

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); } 

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 

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 

• Ordenação de vector
• Quick sort
• Bubble sort
• Selection sort
• TwistSort
• Pesquisa binária
• sort-merge utility
• Heapsort
• Shell sort
• Radix sort

Referências

• «Merge Sort» (em inglês) 
• Merge sort em 13 linguagens
• Merge Sort paralelo em Java (multithreading)

• Portal das tecnologias de informação