Merge Sort

{confronti tra algortitmi}


type INTARRAY = array[1..100000] of integer;

procedure gen_array(var A:INTARRAY; N:integer);
var i:integer;
begin
for i:=1 to N do A[i]:=Random(10*N);
end;

{copia l'array X in Y}
procedure copy_array(var X, Y:INTARRAY; n:integer);
var i:integer;
begin
for i := 0 to N do Y[i] := X[i];
end;

function min(a,b:integer):integer;
begin if a else min := b;
end;

procedure print_array(var A:INTARRAY; N:integer);
var i:integer;
begin
for i:=1 to min(n, 100) do
begin
write(A[i]:6);
if ((i mod 10)= 0) then writeln;
end;
if (n>100) then writeln('......'); //writeln('array troppo lungo da scrivere');
end;

procedure InsSort(var A: INTARRAY; N: integer);
var i, j, t, indM: integer;
begin {Insertion Sort }
for i := 1 to N-1 do
begin
indM:=i;
for j:=i+1 to N do
if A[j] t:= A[i];
A[i]:=A[indM];
A[indM] := t;
end;
end;

procedure Merge (var A: INTARRAY; p, q, r: integer);
var i, j, k: integer;
var B: INTARRAY;
begin { Merge }
i := p;
j := q + 1;
k := p;
while ((i <= q) and (j <= r)) do
begin
if (A[i] < A[j])
then begin
B[k] := A[i];
i := i + 1;
end
else begin
B[k] := A[j];
j := j + 1;
end;
k := k + 1;
end;
while (i <= q) do
begin
B[k] := A[i];
k := k + 1;
i := i + 1;
end;
while (j <= r) do
begin
B[k] := A[j];
k := k + 1;
j := j + 1;
end;
for k := p to r do A[k] := B[k];
end;

procedure MergeSort (var A: INTARRAY; p, r: integer);
var q: integer;
begin { MergeSort }
if (p < r) then
begin
q := (p + r) div 2;
MergeSort (A, p, q);
MergeSort (A, q + 1, r);
Merge (A, p, q, r);
end;
end;


var data: INTARRAY;
var A: INTARRAY;
var i, j, key:integer;


// Programma principale
var N:integer;
begin
write('numero elementi: ');
readln(N);
gen_array(data, N);

copy_array(data, A, N);

writeln('array in input: ');
print_array(data, N);
writeln('pronto ad ordinare con isertion sort: ');
readln;
InsSort(data, N);
writeln('array dopo ordinamento:');
print_array(data, N);

copy_array(A, data, N);
writeln('pronto ad ordinare con merge sort: ');
readln;
MergeSort(data, 1, N);
writeln('array dopo ordinamento:');
print_array(data, N);
writeln('programma finito');
readln;
end.