Merge sort

Merge sort
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)$ auxiliar
Algoritmos

O merge sort, ou ordenação por mistura, é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

Sua idéia básica é muito fácil: criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

Os três passos úteis dos algoritmos dividir-para-conquistar, ou divide and conquer, que se aplicam ao merge sort são:

1. Dividir: Dividir os dados em subsequências pequenas;
2. Conquistar: Classificar as duas metades recursivamente aplicando o merge sort;
3. Combinar: Juntar as duas metades em um único conjunto já classificado.

Características

• Complexidade de tempo: Θ(n log₂ n)
• Complexidade de espaço: Θ(n)

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 Θ(n log n).
• É possível também implementar o algoritmo com espaço adicional Θ(1)
• Algoritmo Criado por Von Neumann em 1945.

Vantagens

• Algoritmo de ordenação de simples implementação e fácil entendimento utilizando chamadas recursivas.

Implementações

C

void merge(int vec[], int vecSize) {
  int mid;
  int i, j, k;
  int* tmp;
 
  tmp = (int*) malloc(vecSize * sizeof(int));
  if (tmp == NULL) {
    exit(1);
  }
 
  mid = vecSize / 2;
 
  i = 0;
  j = mid;
  k = 0;
  while (i < mid && j < vecSize) {
    if (vec[i] < vec[j]) {
      tmp[k] = vec[i];
      ++i;
    }
    else {
      tmp[k] = vec[j];
      ++j;
    }
    ++k;
  }
 
  if (i == mid) {
    while (j < vecSize) {
      tmp[k] = vec[j];
      ++j;
      ++k;
    }
  }
  else {
    while (i < mid) {
      tmp[k] = vec[i];
      ++i;
      ++k;
    }
  }
 
  for (i = 0; i < vecSize; ++i) {
    vec[i] = tmp[i];
  }
 
  free(tmp);
}
 
void mergeSort(int vec[], int vecSize) {
  int mid;
 
  if (vecSize > 1) {
    mid = vecSize / 2;
    mergeSort(vec, mid);
    mergeSort(vec + mid, vecSize - mid);
    merge(vec, vecSize);
  }
}

[Código em C]

# include <stdio.h>
# include <ctype.h>
# include <string.h>
# include <stdlib.h>
 
# define MAX 10000001
# define SWAP(A, B) { int C = A; A = B; B =C }
 
int A[MAX],B[MAX];
void mergesort(int begin, int end);
 
int main (void)
{
        int i = 0, j = 0;
 
        while(scanf("%d",&A[i]) >= 1)
                i++;
 
        mergesort(0,i-1);
 
        for(j = 0;j < i;j++)
                printf("%d\n",A[j]);
 
        return 0;
}
 
void mergesort(int begin, int end)
{
        int left = 0, right = 0, middle = 0;
        int i = 0;
 
        if(begin == end)
                return;
 
        middle = (begin + end)/2;
 
        mergesort(begin,middle);
        mergesort(middle + 1,end);
 
        left = begin;
        right = middle + 1;
 
        for(i = begin;i <= end;i++)
        {
                if(right > end || (left <= middle && A[left] <= A[right]))
                {
                        B[i] = A[left];
                        left++;
                }
                else
                {
                        B[i] = A[right];
                        right++;
                }
        }
        for(i = begin;i <= end;i++)
                A[i] = B[i];
}

Código em C#

    class Merge
    {
        private int[] vet;
        private int numElemen;
 
        public void Merge_sort(int[] valores)
        {
            vet = valores;
            numElemen = valores.Length;
            mergesort(0, numElemen - 1);
        }
 
        private void mergesort(int inicio, int fim)
        {
            // Verifica se o inicio é menor que o fim, se for, o vetor é ordenado
            if (inicio < fim)
            {
                // Obtem o index do elemneto do meio
                int meio = (inicio + fim) / 2;
                // Ordena a parte da esqueda(em relação ao meio) do vetor
                mergesort(inicio, meio);
                // Ordena a parte da direita(em relação ao meio) do vetor
                mergesort(meio + 1, fim);
                // Combina os dois lados ordenados
                merge(inicio, meio, fim);
            }
        }
 
        private void merge(int inicio, int meio, int fim)
        {
 
            // Declara vetor auxiliar
            int[] vetAux = new int[numElemen];
 
            // Copia as duas partes do vetor para o auxiliar
            for (int i = inicio; i <= fim; i++)
            {
                vetAux[i] = vet[i];
            }
 
            int z = inicio;
            int j = meio + 1;
            int k = inicio;
            // Obtem os valores da direita ou da esquerda e copia para o vetor original
            while (z <= meio && j <= fim)
            {
                if (vetAux[z] <= vetAux[j])
                {
                    vet[k] = vetAux[z];
                    z++;
                }
                else
                {
                    vet[k] = vetAux[j];
                    j++;
                }
                k++;
            }
            // Copia o resto dos valores da esquerda e insere no vetor
            while (z <= meio)
            {
                vet[k] = vetAux[z];
                k++;
                z++;
            }
            // Esvazia a memória
            vetAux = null;
        }
    }

Java

/* Vetor de entrada */
 
private int[] vetor;
 
/*
 * Método recursivo que divide o vetor em dois e depois os mescla e ordena
 */
 
private void merge(int inicio, int fim) {
 
        if (inicio < fim) {
                int meio = (inicio + fim) / 2;
                merge(inicio, meio);
                merge(meio + 1, fim);
                mesclar(inicio, meio, fim);
        }
 
}
 
/* 
 * Ordena dois trechos ordenados e adjacente de vetores e ordena-os
 * conjuntamente
 */
private void mesclar(int inicio, int meio, int fim) {
 
        int tamanho = fim - inicio + 1;
 
        /*
         * Inicialização de um vetor temporario para auxiliar na ordenação O
         * vetor temporário é uma cópia do trecho que será ordenado
         */
 
        int[] temp = new int[tamanho];
 
        System.arraycopy(vetor, inicio, temp, 0, tamanho);
 
        /*
         * Laço para ordenação do vetor, utilizando o vetor temporário, usando
         * índices i e j para cada trecho de vetor da mesclagem
         */
 
        int i = 0;
        int j = meio - inicio + 1;
 
        //A depender das condições, recebe um elemento de um trecho ou outro
        for (int posicao = 0; posicao < tamanho; posicao++) {
                if (j <= tamanho - 1) {
                        if (i <= meio - inicio) {
                                if (temp[i] < temp[j]) {
                                        vetor[inicio + posicao] = temp[i++];
                                } else {
                                        vetor[inicio + posicao] = temp[j++];
                                }
                        } else {
                                vetor[inicio + posicao] = temp[j++];
                        }
                } else {
                        vetor[inicio + posicao] = temp[i++];
                }
        }
}

ActionScript 3

/* Vetor de entrada */
 
var vetor:Array = new Array;
 
/*
 * Método recursivo que divide o vetor em dois e depois os mescla e ordena
 */
//trace (vetor);
function merge (inicio:int , fim:int):void
{
        if (inicio < fim)
        {
                var meio:int = (inicio + fim) / 2;
                merge (inicio, meio);
                merge (meio + 1, fim);
                mesclar (inicio, meio, fim);
        }
}
 
/* 
 * Ordena dois trechos ordenados e adjacente de vetores e ordena-os
 * conjuntamente
 */
function mesclar (inicio:int ,meio:int, fim:int):void
{
        var tamanho:int = fim - inicio + 1;
        /*
                 * Inicialização de um vetor temporario para auxiliar na ordenação O
                 * vetor temporário é uma cópia do trecho que será ordenado
                 */
 
        var temp:Array = new Array  ;//int[tamanho];
        ArrayCopy (vetor, inicio, temp, 0, tamanho);
 
 
        /*
                 * Laço para ordenação do vetor, utilizando o vetor temporário, usando
                 * índices i e j para cada trecho de vetor da mesclagem
                 */
 
        var i:int = 0;
        var j:int = meio - inicio + 1;
 
        //A depender das condições, recebe um elemento de um trecho ou outro
        for (var posicao:int = 0; posicao < tamanho; posicao++)
        {
                if (j <= tamanho - 1)
                {
                        if (i <= meio - inicio)
                        {
                                if (temp[i] < temp[j])
                                {
                                        vetor[inicio + posicao] = temp[i++];
                                }
                                else
                                {
                                        vetor[inicio + posicao] = temp[j++];
                                }
                        }
                        else
                        {
                                vetor[inicio + posicao] = temp[j++];
                        }
                }
                else
                {
                        vetor[inicio + posicao] = temp[i++];
                }
        }
}
function ArrayCopy (src:Array,srcInit:int,dest:Array,destInit:int,_length:int):void
{
        var destIniHandler:int = destInit;
        for (var i:int=srcInit; i<(srcInit+_length); i++)
        {
                dest[destIniHandler] = src[i];
                destIniHandler++;
        }
}

Haskell

sort :: Ord a => [a] -> [a]

sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where 
      (ys,zs) =  splitAt (length xs `div` 2) xs
       merge [] y=y
       merge x []=x
       merge (x:xs) (y:ys)
         | x <= y = x:merge xs (y:ys)
         | otherwise = y:merge (x:xs) ys

Python

def merge(lista_x,lista_y):
  if lista_x == []:
       return lista_y
  elif lista_y == []:
       return lista_x
  else:
      if lista_x[0] < lista_y[0]:
          return [lista_x[0]] + merge(lista_x[1:],lista_y)
      else:
          return [lista_y[0]] + merge(lista_x,lista_y[1:])
 
def mergesort(lista):
  if len(lista) <= 1:
     return lista
  else:
      mid = len(lista) // 2
      return merge(mergesort(lista[:mid]), mergesort(lista[mid:]))

Ruby

def sort(array)
  mid = array.length / 2
  mid < 1 ? array : merge(sort(array[0...mid]), sort(array[mid..-1]))
end

R

mergesort=function(x){ # Função que irá quebrar a entrada ao meio cada vez que for acionada
        semisort=function(y,z){ #Função que vai juntando ordenadamente as partes da entrada
                resultado=NULL
                while(length(y)>0 & length(z)>0){ # Enquanto tiver elemento nas duas partes que estou trabalhando
                        if(y[1]<=z[1]){
                                resultado=c(resultado,y[1])
                                y=y[-1] # Tira o primeiro elemento do vetor, já que ele já foi adicionado ao resultado
                        }
                        else{
                                resultado=c(resultado,z[1])
                                z=z[-1] 
                        }
                }
                if(length(y)>0){ # A partir do momento que acaba os elementos em uma das metades, me resta "copiar" o que sobrou  da outra metade
                        resultado=c(resultado,y)
                }
                if(length(z)>0){
                        resultado=c(resultado,z)
                }
                return(resultado) # Retorna o resultado ordenado
        }
        tamanho=length(x) # Se a entrada tiver mais de um elemento, o algoritmo irá "quebrar" a entrada ao "meio" para ordenar individualmente cada entrada e depois juntar as metades já ordenadas
        if(tamanho>1){
                meio= tamanho/2
                esq=x[1:floor(meio)]
                dit=x[floor(meio+1):tamanho]
                esq=mergesort(esq) 
                dit=mergesort(dit)
                if(esq[length(esq)]<=dit[1]){
                        return(c(esq,dit))
                }
                else{
                        semisort(esq,dit)
                }
        }
        else{ # Se a entrada for um unico elemento, a ordenação dela é trivial
                return(x)
        }
}

Miranda

sort []    = []
sort [x]   = [x]
sort array = merge (sort left) (sort right)
             where
               left  = [array!y | y <- [0..mid]]
               right = [array!y | y <- [(mid+1)..max]]
               max   = #array - 1
               mid   = max div 2

Prolog

split([], K, [], []).
split(XS, K, [], XS)            :-
        K < 1.
split([X|XS], K, [X|YS], ZS)    :-
        K >= 1,
        P is K -1,
        split(XS, P, YS, ZS).

merge1([], [], []).
merge1(XS, [], XS).
merge1([], YS, YS).
merge1([X|XS], [Y|YS], [X|ZS])  :-
        X =< Y,
        merge1(XS, [Y|YS], ZS).
merge1([X|XS], [Y|YS], [Y|ZS])  :-
        Y < X,
        merge1([X|XS], YS, ZS).

mergesort([], []).
mergesort([X], [X]).
mergesort([X, Y], [X, Y])       :-
        X =< Y, !.
mergesort([X, Y], [Y, X])       :-
        X > Y, !.
mergesort(XS, ZS)               :-
        length(XS, L),
        L > 0,
        K is L / 2,
        split(XS, K, XS1, XS2),
        mergesort(XS1, YS1),
        mergesort(XS2, YS2),
        merge1(YS1, YS2, ZS), !.

Ver também

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

Ligações externas

• http://c2.com/cgi/wiki?MergeSort
• Merge sort em 13 linguagens