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