相同值，500000个元素：
　　Sort:时间：1.41；比较次数：8401712。
　　QuickSort:时间：1.47；比较次数：9262161。
　　IntroSort:时间：1.40；比较次数：8401712。
　　MergeSort:时间：1.43；比较次数：4766525。

　　波形分布（波长1000），500000个元素：
　　Sort:时间：2.52；比较次数：10658948。
　　QuickSort:时间：2.97；比较次数：12971845。
　　IntroSort:时间：3.02；比较次数：12672744。
　　MergeSort:时间：2.71；比较次数：7978745。

　　峰形分布（前半段为正序，后半段为前半段的逆转），500000个元素：
　　Sort:时间：2.42；比较次数：10401407。
　　IntroSort:时间：5.13；比较次数：19211813。
　　MergeSort:时间：1.88；比较次数：5176855。

　　谷形分布（峰形分布的逆转），500000个元素：
　　Sort:时间：2.29；比较次数：10944792。
　　IntroSort:时间：5.29；比较次数：17898801。
　　MergeSort:时间：1.90；比较次数：5282136。

　　由于这个排序的最差分布不是很好寻找，我修改了一下Partition函数，使正序分成成为它的不利分布，然后在同一台机器上测了一下：

　　正序分布，500000个元素：
　　Sort:时间：2.77；比较次数：12011738。
　　IntroSort:时间：4.31；比较次数：19212426。
　　MergeSort:时间：1.73；比较次数：4766525。

　　{**************************************************************************
　　函数：Merge
　　功能：将两个有序序列合并为一个有序列序。
　　参数：
　　SrcFirst, SrcSecond: PPointerList，两个源序列。合并时如果有相同的值，
　　SrcSecond的值将排在SrcFirst的值的后面。
　　Dest：PPointerList，存放合并结果的序列，必须有足够的空间。
　　SizeFirst, SizeSecond: Integer, 两个源序列长度
　　LessThen: TLessThenProc，用于定义顺序的比较函数
　　**************************************************************************}

　　procedure Merge(SrcFirst, SrcSecond, Dest: PPointerList;
　　SizeFirst, SizeSecond: Integer; LessThen: TLessThenProc);
　　var
　　I: Integer;
　　IsFirst: Boolean;
　　begin
　　IsFirst := True;
　　if (SizeFirst = 0) or (LessThen(SrcSecond[0], SrcFirst[0])) then
　　begin
　　Swap(Pointer(SrcFirst), Pointer(SrcSecond));
　　Swap(SizeFirs, SizeSecond);
　　IsFirst := not IsFirst;
　　end;
　　while SizeFirst > 0 do
　　begin
　　if SizeSecond = 0 then
　　I := SizeFirst
　　else
　　begin
　　I := 0;
　　while (I < SizeFirst) and
　　((IsFirst and not LessThen(SrcSecond[0], SrcFirst[I]))
　　or (not IsFirst and LessThen(SrcFirst[I], SrcSecond[0]))) do
　　Inc(I);
　　end;
　　Move(SrcFirst^, Dest^, Sizeof(Pointer) * I);
　　Dec(SizeFirst, I);
　　SrcFirst := @SrcFirst[I];
　　Dest := @Dest[I];
　　Swap(Pointer(SrcFirst), Pointer(SrcSecond));
　　Swap(SizeFirst, SizeSecond);
　　IsFirst := not IsFirst;
　　end;
　　end;

{**************************************************************************
　　函数：SortInsert
　　功能：向有序序列中插入一个值，保证插入后仍然有序。
　　参数：
　　Data: PPointerList，有序序列，必须可容纳Size + 1个元素
　　Size: Integer, 原序列长度
　　Value: 新插入的值
　　LessThen: TLessThenProc，用于定义顺序的比较函数
　　**************************************************************************}
　　procedure SortInsert(Data: PPointerList; Size: Integer; Value: Pointer; LessThen: TLessThenProc);
　　var
　　J: Integer;
　　begin
　　if LessThen(Value, Data[0]) then
　　J := 0
　　else
　　begin
　　J := Size;
　　while (J > 0) and LessThen(Value, Data[J - 1]) do
　　Dec(J);
　　end;
　　Move(Data[J], Data[J +1], Sizeof(Pointer) * (Size - J));
　　Data[J] := Value;
　　　　end;
　　{**************************************************************************
　　函数：MergePart
　　功能：将序列中的两个邻近有序子序列合并为一个有序子序列并存放在原处。
　　参数：
　　Data: PPointerList，源序列。
　　PartSize: Integer, 第一个有序子序列长度。
　　Size: Integer, 序列总长度。
　　LessThen: TLessThenProc，用于定义顺序的比较函数
　　说明：
　　如果自由空间足够，调用Merge实现，否则调用SortInsert。
　　**************************************************************************}
　　procedure MergePart(Data: PPointerList; First: Integer; Size: Integer;LessThen: 　　TLessThenProc);
　　var
　　Buffer: PPointerList;
　　I: Integer;
　　begin
　　Buffer := AllocMem(Size * Sizeof(Pointer));
　　if Buffer <> nil then
　　begin
　　Move(Data^, Buffer^, Size * Sizeof(Pointer));
　　Merge(@Buffer[0], @Buffer[First], Data, First, Size-First, LessThen);
　　FreeMem(Buffer);
　　end
　　else
　　begin
　　Dec(Size);
　　for I := PartSize to Size do
　　SortInsert(Data, I, Data[I], LessThen);
　　end;
　　end;
　{**************************************************************************
　　函数：InsertionSort
　　功能：简单插入排序
　　参数：
　　Data: PPointerList，源序列。
　　Size: Integer, 序列长度。
　　LessThen: TLessThenProc，用于定义顺序的比较函数
　　**************************************************************************}
　　procedure InsertionSort(Data: PPointerList; Size: Integer;
　　LessThen: TLessThenProc);
　　var
　　I: Integer;
　　begin
　　Dec(Size);
　　for I := 1 to Size do
　　SortInsert(Data, I, Data[I], LessThen);
　　end;
　　{**************************************************************************
　　函数：Sort
　　功能：排序
　　参数：
　　Data: PPointerList，源序列。
　　Size: Integer, 序列长度。
　　LessThen: TLessThenProc，用于定义顺序的比较函数
　　说明：
　　使用快速排序。
　　当子序列长度不大于SORT_MAX时使用插入排序。
　　当子序列长度比大于MAX_RATIO时将长子序列一分为二分别排序，然后合并。
　　**************************************************************************}
　　procedure Sort(Data: PPointerList; Size: Integer; LessThen: TLessThenProc);
　　var
　　M: Integer;
　　OtherData: PPointerList;
　　OtherSize: Integer;
　　　　begin
　　Assert(Data <> nil);
　　while Size > SORT_MAX do
　　begin
　　M := Partition(Data, Size, LessThen);
　　if (M <= Size div 2) then
　　begin
　　　　OtherData := @Data[M + 1];
　　　　OtherSize := Size - M - 1;
　　　　Size := M;
　　end
　　else
　　begin
　　OtherData := Data;
　　OtherSize := M;
　　Data := @OtherData[M + 1];
　　Size := Size - M - 1;
　　end;

　　if (OtherSize div MAX_RATIO > Size) then
　　begin
　　M := OtherSize div 2;
　　Sort(OtherData, M, LessThen, MaxRatio);
　　Sort(@OtherData[M], OtherSize - M, LessThen, MaxRatio);
　　MergePart(OtherData, M, OtherSize, LessThen);
　　end
　　else
　　　　Sort(OtherData, OtherSize, LessThen, MaxRatio);
　　end;
　　InsertionSort(Data, Size, LessThen);
　　end;