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

void MergeVettoreOttimizzato(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.
     Versione ottimizzata che evita di effettuare una doppia copia degli
     elementi finali di uno dei sottovettori.
  */
{
  TipoVettore B;   /* vettore di appoggio */
  int primo, secondo, appoggio, i;

  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++;
  }

  /* parte finale ottimizzata */

  if (secondo > finale)           /* e` finito prima il secondo sottovettore;
                                     copia da A in A stesso tutti gli elementi
                                     fino a mediano, incominciando dal basso */
    for (i = mediano; i >= primo; i--) {
      A[finale] = A[i];
      finale--;
    }

  /* NON c'e' il ramo else */

              /* copia tutti gli elementi da iniziale a appoggio-1 da B ad A */
  for (i = iniziale; i <= appoggio - 1; i++)
    A[i] = B[i];
}  /* MergeVettoreOttimizzato */


void MergeRicorsivoOttimizzato(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.
     Utilizza la versione ottimizzata della funzione per effettuare il merge.
  */
{
  int mediano;

  int i;

  if (iniziale < finale) {
    mediano = (iniziale + finale) / 2;

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

/*
    printf("merge %d-%d [ ", iniziale, mediano);
    for (i = iniziale; i <= mediano; i++)
      printf("%d ", A[i]);
    printf("] con %d-%d [ ", mediano + 1, finale);
    for (i = mediano + 1; i <= finale; i++)
      printf("%d ", A[i]);
    printf("] ==> [ ");
*/

    MergeVettoreOttimizzato(A, iniziale, mediano, finale);

/*
    for (i = iniziale; i<= finale; i++)
      printf("%d ", A[i]);
    printf("]\n");
*/
  }
}  /* MergeRicorsivo */


void MergeSortOttimizzato(TipoVettore A, int n)
  /* Ordina i primi n elementi del vettore A usando l'algoritmo di ordinamento
     per fusione.
     Utilizza la versione ottimizzata della funzione per effettuare il merge.
  */
{
  MergeRicorsivoOttimizzato(A, 0, n-1);
}  /* MergeSortOttimizzato */