ALGORITMO MERGESORT

Ainda existe uma discussão sobre o assunto, mas apareceram evidências de que o algoritmo mergesort foi proposto por John Von Neumann em 1945. Essa discussão existe, pois estudar as várias contribuições que ele fez é, ao mesmo tempo, complexa e fascinante. Essa complexidade devesse em parte a existência de muitas fontes de informação, algumas pouco acessíveis, outras discordantes entre si ou polêmicas. A atribuição a ele veio de Knuth, que argumentou no seu livro ‘Arte de Programação Computacional: Ordenando e Procurando’ que Von Neumann foi o primeiro a descrever a idéia.

GIACON, André P., et al. MERGESORT. Faculdade de Tecnologia - Unicamp, 2010

void mergesort(int *vet,int inicio,int fim){     

     if(inicio == fim ) { return; }     

     int meio = (inicio + fim )/2;     

     mergesort(vet, inicio, meio );

     mergesort(vet, meio + 1, fim);

     int k = 0;

     int i = inicio;

     int j = meio + 1;

     //A linha abaixo cria um novo vetor auxiliar

     int *vetaux = (int *) malloc(sizeof (int) * (fim-inicio+1));     

     while( i < meio + 1 || j < fim + 1 ) {

           if( i == meio + 1 ) {

               vetaux[k] = vet[j];

               j++;

               k++;

           }else{

                 if ( j == fim + 1 ) {

                      vetaux[k] = vet[i];

                      i++;

                      k++;

                 }else{

                       if( vet[i] < vet[j] ) {

                           vetaux[k] = vet[i];

                           i++;

                           k++;

                       }else{

                             vetaux[k] = vet[j];

                             j++;

                             k++;

                       }

                 }

           }

     }

     //Este laco copia o vetor auxiliar no vetor principal

     for( i = inicio; i <= fim; i++ ){

          vet[i] = vetaux[i - inicio];

     }

}