MergeSort

Třídění slučováním

 

Tento algoritmus rozdělí pole na dvě přibližně stejně velké části.Pote s každou z těchto částí učiní totéž-rozdelí na dvě...dokud nedostaneme jednoprvkové ůseky. Jednopoložkové ůseky jsou vždy utříděné, takže ted bereme utříděné ůseky a slučujeme tak, aby byly zase utříděné...Končíme až když uspořádáme celé pole .

3
5
2
1
4
10
8
6
3
-
5
-
2
-
1
-
4
-
10
-
8
-
6
3
5
-
1
2
-
4
10
-
6
8
1
2
3
5
-
4
6
8
10
1
2
3
4
5
6
7
8

 

Takto vypadá Mergesort v Delphi

 

var
Setridene : TPoleCisel;
PPole : ^TPoleCisel;

 

procedure Merge(l,q,r : integer);

var i,j,k : integer;

begin

i := l;
j := q+1;

for k := l to r do
begin
if (i <= q) and ((j > r) or (PPole^[i] <= PPole^[j])) then

begin
Setridene[k] := PPole^[i];
inc(i);
end

else
if j <= r then
begin
Setridene[k] := PPole^[j];
inc(j);

end;
end;

for i := l to r do
PPole^[i] := Setridene[i];

end;

 

 

procedure MSort(l,r : integer);

var
q : integer;

begin
if l < r then

begin
q := trunc((l+r) / 2);
MSort(l,q); //rozdelí pole
MSort(q+1,r); //rozdelí pole
Merge(l,q,r); //sloučí pole

end;
end;

 

procedure MergeSort(var Pole : TPoleCisel);

begin

PPole := @Pole;
MSort(0,length(pole));

end;