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

#define TAMANHO 10

/* Intercala as sequencias v[p]..v[q-1] e v[q]..v[r] */
void intercala (int p, int q, int r, int v[]) {
  int i, j, k;
  int w[TAMANHO];

  i = p; 
  j = q;
  k = 0;

  while (i < q && j <= r) {
	if (v[i] <= v[j]){
      	   w[k] = v[i];
           k++;
           i++; 
	}else{
           w[k] = v[j];
           k++;
           j++;  
	}  
  }

  //se a metade da esquerda tem os maiores elementos do vetor
  while (i < q){  
    	w[k] = v[i];
    	k++;
    	i++;
   }
  //se a metade da direita tem os maiores elementos do vetor
  while (j <= r){  
  	  w[k] = v[j];
   	 k++;
   	 j++; 
  }

  //copia o vetor auxiliar w para o vetor original v 
  for (i = p; i <= r; i++)  
    	v[i] = w[i-p];
}


void mergesort (int p, int r, int v[]) {
  if (p < r) {
    int q = (p + r)/2;
    //sublista da esquerda
    printf("merge esqueda \n");
    mergesort (p, q, v);
    //sublista da direita
    printf("merge direita \n");
    mergesort (q + 1, r, v);
    //intercala as sublistas
    printf("intercala \n");
    intercala (p, q + 1, r, v);
  }
}

int main () {
  
  int vetor[TAMANHO] = {37,54,21,68,91,2,51,64,34,25};
  int i;

  mergesort (0, TAMANHO - 1, vetor);
  
  printf ("{%d", vetor[0]);
  
  for (i = 1; i < TAMANHO; i++) {
    printf (", %d", vetor[i]);
  }

  printf ("}\n");
  
  system("pause");
  return 0;
}