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
| type
// Doit retourner
// -1 si Obj1 < Obj2 (ou une propriété de l'objet)
// 0 si Obj1 = Obj2
// +1 si Obj1 > Obj2
TItemCompare = function (Obj1, Obj2: TObject): Integer;
procedure MergeSort(AList : TList; AComparator: TItemCompare);
var
TempList : PPointerList;
SortedList : PPointerList;
procedure Merge(MinIndex,Middle,MaxIndex : Integer);
var
i,j,k : Integer;
begin
// Copie la moitié de la liste dans une liste temporaire
System.Move(SortedList^[MinIndex], TempList^[0],
(Middle - MinIndex+1) * SizeOf(Pointer));
i := 0;
j := Middle+1;
k := MinIndex;
// copy back next-greatest element at each time
while (k<j) and (j<=MaxIndex) do
begin
if AComparator(TObject(TempList^[i]),TObject(SortedList^[j])) <= 0 then
begin
SortedList^[k] := TempList^[i];
Inc(i);
end
else
begin
SortedList^[k] := SortedList^[j];
Inc(j);
end;
Inc(k);
end;
// copy back remaining elements of first half (if any)
while (k<j) do
begin
SortedList^[k] := TempList^[i];
Inc(k);
Inc(i);
end;
end;
procedure MergeDivide(MinIndex,MaxIndex : Integer);
var
Middle : Integer;
begin
if (MinIndex < MaxIndex) then
begin
Middle := (MaxIndex+MinIndex) shr 1;
MergeDivide(MinIndex, Middle);
MergeDivide(Middle+1, MaxIndex);
Merge(MinIndex, Middle, MaxIndex);
end;
end;
begin
SortedList := AList.FList.List;
// Alloue un espace mémoire suffisant pour stocker la moitié des éléments
// de la liste
GetMem(TempList,SizeOf(Pointer)*((AList.Count shr 1)+1));
MergeDivide(0,AList.Count-1);
FreeMem(TempList);
end; |
Partager