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

#define TAMANHO 16

void mostra_vetor(int v[]) {
  int i, j;
  for (j = 0; j <= 4* TAMANHO; j++) 
  	printf("-");    

  printf("\n");
  printf ("{  %2d", v[0]);
  
  for (i = 1; i < TAMANHO; i++) {
   	printf (", %2d", v[i]);
  }

  printf ("}\n");
}

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

int main () {
  
  int vetor[TAMANHO] = {2,4,5,7,9,11,13,15,0,1,3,6,8,10,12,14};

  mostra_vetor(vetor);
  intercala(0, TAMANHO/2, TAMANHO-1, vetor);
  mostra_vetor(vetor);
  
  
  return 0;
}