Merge sort

Merge sort
algoritmo mergesort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	$\Theta (n\log n)$
complexidade caso médio	$\Theta (n\log n)$
complexidade melhor caso	$\Theta (n\log n)$ típico, $\Theta (n)$ variante natural
complexidade de espaços pior caso	$\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). Como o algoritmo Merge Sort usa a recursividade, há um alto consumo de memória e tempo de execução, tornando esta técnica não muito eficiente em alguns problemas.

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 $\Theta (1)$ ;
Conquistar: Recursivamente resolve dois subproblemas, cada um de tamanho n/2, o que contribui com $2T(n/2)$ para o tempo de execução;
Combinar: Unir os sub-arranjos em um único conjunto ordenado, que leva o tempo $\Theta (n)$

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

Complexidade

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

Demonstração da complexidade de tempo

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

${\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 $T(1)=T\left({\frac {n}{n}}\right)=\Theta (1)$ teremos que fazer com que ${2^{h}}=n\Rightarrow \lg {2^{h}}=\lg n\Rightarrow h=\lg n$

Então:

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

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^[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	$O(n\log _{2}n)$	$O(n\log _{2}n)$	$O(n\log _{2}n)$
Quick sort	$O(n\log n)$	$O(n\log n)$	$O(n^{2})$
Bubble sort	$O(n)$	$O(n^{2})$	$O(n^{2})$
Insertion sort	$O(n)$	$O(n^{2})$	$O(n^{2})$
Selection sort	$O(n^{2})$	$O(n^{2})$	$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 $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 $O(n)$ ^[3]. O Quick sort pode atingir um tempo de $O(n^{2})$ em um caso específico quando o particionamento é desequilibrado.

Observações

É 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 $\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 $\Theta (1)$ .
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 $O(n\log n)$ .

Implementações do Mergesort

Pseudocódigo

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

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

Referências

↑ Felipe, Henrique (1 de julho 2018). «Merge Sort». Blog Cyberini. Consultado em 6 de julho de 2018
↑ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2012). Algoritmos: teoria e prática 3 ed. Rio de Janeiro: Elsevier. ISBN 9788535236996
↑ Felipe, Henrique (19 de fevereiro de 2018). «Bubble Sort». Blog Cyberini. Consultado em 6 de julho de 2018