Merge sort

Origem: Wikipédia, a enciclopédia livre.

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 é que é 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:

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

Índice

1 Características
- 1.1 Observações
2 Implementações
- 2.1 C
- 2.2 Java
- 2.3 Haskell
- 2.4 Python
- 2.5 Ruby
- 2.6 Miranda
- 2.7 Prolog
3 Ver também
4 Ligações externas

[editar] Características

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

[editar] 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).
É possível também implementar o algoritmo com espaço adicional Θ(1)

[editar] Implementações

[editar] C

void mergeSort(int vetor[],int aux[],int tam) {
   m_sort(vetor,aux,0,tam-1);
}
 

void m_sort(int vetor[],int aux[],int esq,int dire) {

   int meio;
   if (dire>esq) {
       meio=(dire+esq)/ 2;
       m_sort(vetor,aux,esq,meio);
       m_sort(vetor,aux,meio+1,dire);
       merge(vetor,aux,esq,meio+1,dire);
   }
}


void merge(int vetor[],int aux[],int esq,int meio,int dire) {

   int i,esq_fim,num_elementos,aux_pos;

   esq_fim=meio-1;
   aux_pos=esq;
   num_elementos=dire-esq+1;

   while ((esq<=esq_fim)&&(meio<=dire)) {
 
    if (vetor[esq]<=vetor[meio]) {
   
      aux[aux_pos]=vetor[esq];
      aux_pos=aux_pos+1;
      esq=esq+1;
    }
    else {
   
      aux[aux_pos]=vetor[meio];
      aux_pos=aux_pos + 1;
      meio=meio+1;
    }
   }

 while (esq<=esq_fim) {
 
   aux[aux_pos]=vetor[esq];
   esq=esq+1;
   aux_pos=aux_pos+1;
 }

 while (meio<=dire) {
 
   aux[aux_pos]=vetor[meio];
   meio=meio+1;
   aux_pos=aux_pos+1;
 }

 for (i=0;i<num_elementos;i++) {
 
   vetor[dire]=aux[dire];
   dire=dire-1;
 }
}

[editar] Java

        /*
        * int [] x     ===== vetor a ser ordenado
        * int [] xTemp ===== vetor auxiliar de mesmo tamanho ( obs: precisa ser inicializado )
        * int esq      ===== posição inicial, ou seja, 0
        * int dir      ===== posição final , x.length -1
        */
        public static void mergeSort(int [ ] x,int [ ] xTemp, int esq, int dir)
        {
                if(esq < dir)
                {
                        int medio = (esq + dir)/2;
                        mergeSort(x,xTemp,esq,medio);
                        mergeSort(x,xTemp,medio+1,dir);
                        mezclar(x,xTemp,esq,medio+1,dir);
                }
        }
        
        public static void mezclar (int [ ] x,int [ ] xAux,int posEsq, int posDir,int posFin)
        {
                int finIzq = posDir - 1;
                int posAux = posEsq;
                int numElementos = posFin - posEsq +1;
                // Busca principal
                while(posEsq <= finIzq && posDir <= posFin)
                        if( x[posEsq] < x[posDir] )
                                xAux[posAux++] = x[posEsq++];
                        else
                                xAux[posAux++] = x[posDir++];
                        // Copia primeira metade
                        while (posEsq <= finIzq)
                                xAux[posAux++] = x[posEsq++];
                        // Copia segunda metade
                        while (posDir <= posFin)
                                xAux[posAux++] = x[posDir++];
                        // Copia veteor temporário no principal
                        for(int i = 0; i < numElementos; i++, posFin--)
                                x[posFin] = xAux[posFin];
                }
        }

[editar] Haskell

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

sort []         =  []
sort [x]        =  [x]
sort xs         =  merge (sort ys) (sort zs)
  where 
      merge (ys,zs) =  splitAt (length xs `div` 2) xs

[editar] Python

def sort(array):
  if len(array) <= 1: return array
  mid = len(array) // 2
  return merge (sort(array[0:mid]), sort(array[mid:]))

[editar] Ruby

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

[editar] 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

[editar] 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), !.