/* File: ordmerge.c */
/* Time-stamp: "2001-05-25 16:08:08 calvanes" */
/* Scopo: funzioni sui vettori */

void MergeVettore(TipoVettore A, int iniziale, int mediano, int finale)
  /* Fonde i due sottovettori ordinati di A da iniziale a mediano e
     da mediano+1 a finale in un unico sottovettore ordinato. */
{
  TipoVettore B;                                      /* vettore di appoggio */
  int primo, secondo, appoggio, da_copiare;

  primo = iniziale;
  secondo = mediano + 1;
  appoggio = iniziale;

  while (primo <= mediano && secondo <= finale) {
    if (A[primo] <= A[secondo]) {
      B[appoggio] = A[primo];
      primo++;
    }
    else {
      B[appoggio] = A[secondo];
      secondo++;
    }
    appoggio++;
  }

  if (secondo > finale)             /* e` finito prima il secondo sottovettore;
                                       copia da A in B tutti gli elementi del
                                       primo sottovettore fino a mediano */
    for (da_copiare = primo; da_copiare <= mediano; da_copiare++) {
      B[appoggio] = A[da_copiare];
      appoggio++;
    }
  else                              /* e` finito prima il primo sottovettore
                                       copia da A in B tutti gli elementi del
                                       secondo sottovettore fino a finale */
    for (da_copiare = secondo; da_copiare <= finale; da_copiare++) {
      B[appoggio] = A[da_copiare];
      appoggio++;
    }
                /* ricopia tutti gli elementi da iniziale a finale da B ad A */
  for (da_copiare = iniziale; da_copiare <= finale; da_copiare++)
    A[da_copiare] = B[da_copiare];
} /* MergeVettore */


void MergeRicorsivo(TipoVettore A, int iniziale, int finale)
  /* Ordina gli elementi del vettore A di indice compreso tra iniziale e finale
     usando l'algoritmo di ordinamento per fusione. */
{
  int mediano;

  if (iniziale < finale) {        /* l'intervallo da iniziale a finale, estremi
                                     inclusi comprende almeno due elementi */
    mediano = (iniziale + finale) / 2;

    MergeRicorsivo(A, iniziale, mediano);
    MergeRicorsivo(A, mediano+1, finale);

    MergeVettore(A, iniziale, mediano, finale);
  }
}  /* MergeRicorsivo */


void MergeSort(TipoVettore A, int n)
  /* Ordina i primi n elementi del vettore A usando l'algoritmo di ordinamento
     per fusione. */
{
  MergeRicorsivo(A, 0, n-1);
}  /* MergeSort */