MergeSort.c

/*
*	Exemplo de Ordenação utilizando Merge Sort
*
*	Dividir para conquistar:
*
*	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.
*
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TAM_VETOR 100

void merge(int vetor[], int tamanho) {
  int meio = tamanho / 2;
  int i = 0, j = meio, k = 0;
  int aux[tamanho];

  while( i < meio && j < tamanho ){
    if( vetor[i] <= vetor[j] )
      aux[k] = vetor[i++];
    else
      aux[k] = vetor[j++];
    k++;
  }
 
  if( i == meio )
    while( j < tamanho )
      aux[k++] = vetor[j++];
  else
    while( i < meio )
      aux[k++] = vetor[i++];
 
  for( i = 0; i < tamanho; i++ )
    vetor[i] = aux[i];
}
 
int mergeSort(int vetor[], int tamanho){
	int meio = tamanho / 2;

	if( tamanho > 1 ){
		mergeSort(vetor, meio);
		mergeSort(vetor + meio, tamanho - meio);
		merge(vetor, tamanho);
	}

}

int main(){

	int vetor[TAM_VETOR];
	
	// Preenche o vetor com valores aleatórios 0-1000
	srand(time(NULL));
	for(int i = 0; i < TAM_VETOR; i++){
		vetor[i] = rand()%1000;
		printf("%d, ", vetor[i]);
	}
	
	printf("\n\n");
	
	mergeSort(vetor, TAM_VETOR);

	for(int i = 0; i < TAM_VETOR; i++){
		printf("%d, ", vetor[i]);
	}
	
	return 0;
}