{ File: ordmerge.pas }

{ Scopo: ordinamento per fusione di un vettore }

{ E` richiesta la definizione preliminare di:

const
  NumElementi = ...;

type
  TipoElemento = ...;
  TipoIndice   = 1..NumElementi;
  TipoVettore  = array [TipoIndice] of TipoElemento;

}

procedure MergeSort (var A: TipoVettore);
{ Ordina il vettore A usando l'algoritmo di ordinamento per fusione. }


  procedure MergeVettore (var A: TipoVettore;
                          iniziale, mediano, finale: TipoIndice);
  { Effettua la fusione degli elementi compresi nei due sottovettori
    A[iniziale..mediano] e A[mediano..finale] nell'unico sottovettore
    A[iniziale..finale]. }
  var
    B                        : TipoVettore;       { vettore di appoggio }
    primo, secondo, appoggio : integer;
    da_copiare               : TipoIndice;

  begin { MergeVettore }
    primo := iniziale;
    secondo := mediano + 1;
    appoggio := iniziale;
  
    while (primo <= mediano) and (secondo <= finale) do
    begin
      if (A[primo] <= A[secondo]) then
      begin
         B[appoggio] := A[primo];
         primo := primo + 1
      end
      else
      begin
        B[appoggio] := A[secondo];
        secondo := secondo + 1
      end;
      appoggio := appoggio + 1;
    end; { while }
  
    if secondo > finale then     { e' finito prima il secondo sotto-vettore }
      { copia da A in B tutti gli elementi del primo vettore fino a mediano }
      for da_copiare := primo to mediano do
      begin
        B[appoggio] := A[da_copiare];
        appoggio := appoggio + 1
      end
    else                         { e' finito prima il primo sotto-vettore }
      { copia da A in B tutti gli elementi del secondo vettore fino a finale }
      for da_copiare := secondo to finale do
      begin
        B[appoggio] := A[da_copiare];
        appoggio := appoggio + 1
      end;
  
    { ricopia tutti gli elementi da iniziale a finale da B ad A }
    for da_copiare := iniziale to finale do
      A[da_copiare] := B[da_copiare]
  end; { MergeVettore }


  procedure MergeRicorsivo (var A: TipoVettore;
                            iniziale, finale: TipoIndice);
  { Effettua l'ordinamento del sottovettore A[iniziale..finale]. }
  var
    mediano : TipoIndice;

  begin { MergeRicorsivo }
    if iniziale < finale then
       { esiste almeno un elemento tra iniziale e finale }
    begin
      mediano := (iniziale + finale) div 2;

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

      MergeVettore(A, iniziale, mediano, finale)
    end
  end; { MergeRicorsivo }


begin { MergeSort }
  MergeRicorsivo(A, 1, NumElementi)
end; { MergeSort }