1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
unit UMergeSort;
interface
type
TDirection = (dSourceSource, dSourceTemp, dTempTemp, dTempSource);
TCompareProc = function(TempIndex, SourceIndex: integer): boolean; cdecl;
PCompareProc = ^TCompareProc;
TCopyProc = function(iSourceIndex, iDestIndex: integer; bDirection: TDirection): boolean; cdecl;
PCopyProc = ^TCopyProc;
TMergeSorter = class
private
n: integer;
aCallbackCompare: TCompareProc;
aCallbackCopy: TCopyProc;
procedure MergeSort(lo, hi: integer);
procedure Merge(lo, m, hi: integer);
public
procedure Sort(n: integer; aCompare: TCompareProc; aCopy: TCopyProc);
end;
implementation
procedure TMergeSorter.Sort(n: integer; aCompare: TCompareProc; aCopy: TCopyProc);
begin
Self.n := n;
Self.aCallbackCompare := aCompare;
Self.aCallbackCopy := aCopy;
MergeSort(0, n-1);
end;
procedure TMergeSorter.MergeSort(lo, hi: integer);
var
m: integer;
begin
if (lo<hi) then
begin
m := (lo+hi) div 2;
MergeSort(lo, m);
MergeSort(m+1, hi);
Merge(lo, m, hi);
end;
end;
procedure TMergeSorter.Merge(lo, m, hi: integer);
var
i, j, k: integer;
begin
i := 0;
j := lo;
// vordere H�lfte von a in Hilfsarray b kopieren
while (j<=m) do
begin
aCallbackCopy(j, i, dSourceTemp);
//b[i] := a[j];
inc(i);
inc(j);
end;
i := 0;
k := lo;
// jeweils das n�chstgr��te Element zur�ckkopieren
while ((k<j) and (j<=hi)) do
begin
if aCallbackCompare(i, j) then
//if (b[i]<=a[j]) then
begin
aCallbackCopy(i, k, dTempSource);
//a[k] := b[i];
inc(k);
inc(i);
end else
begin
aCallbackCopy(j, k, dSourceSource);
//a[k] := a[j];
inc(k);
inc(j);
end;
end;
// Rest von b falls vorhanden zur�ckkopieren
while (k<j) do
begin
aCallbackCopy(i, k, dTempSource);
//a[k] := b[i];
inc(k);
inc(i);
end;
end;
end.
|
