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

#define SIZE 6

void mergesort(int *, int , int );
void merge(int *, int, int, int);


int main()
{
  
  int v[SIZE];
  int i;
  
  // Inizializzo il vettore
  v[0] = 6;
  v[1] = 2;
  v[2] = 5;
  v[3] = 1;
  v[4] = 3;
  v[5] = 9;
  
  printf("SIZE = %d\n\n", SIZE);
  printf("VETTORE INIZIALE:\n");
  for(i = 0; i < SIZE; i++)
    printf("v[%d] = %d\n", i, v[i]);
  
  // Utilizzo la finzione mergsort
  mergesort(v, 0, SIZE - 1);
  
  // Stampo
  printf("VETTORE FINALE:\n");
  for(i = 0; i < SIZE; i++)
    printf("v[%d] = %d\n",i, v[i]);
  
  return 0;
}


// v = vettore elementi
// i = indice iniziale
// j = indice finale

void mergesort(int *v, int i, int j)
{
  if (i < j){
    int m = (i + j) / 2;
    mergesort(v, i, m);
    mergesort(v, m+1, j);
    merge(v, i, j, m);
  }
}

// v[] = vettore da fondere
// i = indice iniziale sottovettore 1 (INIZIO)
// f = indice finale sottovettore 2 (FINE)
// m = indice finale sottovettore 1 (FINE i) 
// m + 1 = iniziale sottovettore 2 (INIZIO f)

void merge(int *v, int i, int f, int m)
{
  int v1[SIZE]; //creo un vettore v1[SIZE] di appoggio (SIZE= dimensione vettore d'origine)
  int j; 
  int p1 = i;
  int p2 = m + 1;
  
  for(j = p1; j <= f; j++){
    // SE oltrepasso la fine del 1° sotto-vettore
    // copio nel vettore d'appoggio il successivo valore del 2° sotto-vettore
    if (p1 > m)
      v1[j] = v[p2++];
    // SENNO' SE oltrepasso la fine del 2° sotto-vettore
    // copio nel vettore d'appoggio il successivo valore del 1° sotto-vettore
    else if (p2 > f) 
      v1[j] = v[p1++];
    else if (v[p1] < v[p2]){
      v1[j] = v[p1++];
    }
    else 
      v1[j] = v[p2++];
  }
  
  // Copio il vettore d'appoggio nel vettore v[]
  for(j = i; j <= f; j++)
    v[j] = v1[j];
  
}