免责声明：这是一个需要解释代码和算法的问题它不是为了修正或优化任何东西，而是为了促进理解。
我对分类程序的理解不是很好。我请求帮助将已经可用的mergesort代码从integer type转换到string type，这里是：delphi mergesort for string arrays。收到我的答复后，我开始了解整理程序。
有几个资源可以帮助理解：
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/merge/mergen.htm
http://www.youtube.com/watch?v=9Qk1t66g7IU
我试着剖析代码来遵循它。这个问题不是我试图验证自己对mergesort的理解，而是以一种清晰的方式显示排序例程。这个问题的价值在于让人们更好地理解mergesort。这一点很重要，因为如果你很好地理解了一个原型，其他类型的东西就可以更容易理解。
我的问题是为什么我们加上“1”来设置长度和“结果”
SetLength(AVals, Length(Vals) div 2 + 1);
Result := 1 + PerformMergeSort(0, High(Vals));
为什么我们要在这里减去“1”编辑：我认为如果不减去1，k将超出界限？
Result := k - 1;
下面是这个问题的代码；顺便说一下，这是一个优化的合并排序，因为它只复制了一半的数组：
function MergeSortRemoveDuplicates(var Vals: array of Integer):Integer;
var
AVals: array of Integer;
//returns index of the last valid element
function Merge(I0, I1, J0, J1: Integer):Integer;
var
i, j, k, LC:Integer;
begin
LC := I1 - I0;
for i := 0 to LC do
AVals[i]:=Vals[i + I0];
//copy lower half or Vals into temporary array AVals
k := I0;
i := 0;
j := J0;
while ((i <= LC) and (j <= J1)) do
if (AVals[i] < Vals[j]) then begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end else if (AVals[i] > Vals[j]) then begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end else begin //duplicate
Vals[k] := AVals[i];
inc(i);
inc(j);
inc(k);
end;
//copy the rest
while i <= LC do begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end;
if k <> j then
while j <= J1 do begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end;
Result := k - 1;
end;
//returns index of the last valid element
function PerformMergeSort(ALo, AHi:Integer): Integer; //returns
var
AMid, I1, J1:Integer;
begin
//It would be wise to use Insertion Sort when (AHi - ALo) is small (about 32-100)
if (ALo < AHi) then
begin
AMid:=(ALo + AHi) shr 1;
I1 := PerformMergeSort(ALo, AMid);
J1 := PerformMergeSort(AMid + 1, AHi);
Result := Merge(ALo, I1, AMid + 1, J1);
end else
Result := ALo;
end;
begin
SetLength(AVals, Length(Vals) div 2 + 1);
Result := 1 + PerformMergeSort(0, High(Vals));
end;
以下是我的理解，只是稍加修改：
function MergeSortRemoveDuplicates(var Vals: array of Integer):Integer;
var
AVals: array of Integer;
//returns index of the last valid element
function Merge(I0, I1, J0, J1: Integer):Integer;
var
i, j, k, LC:Integer;
begin
// difference between mid-point on leftside
// between low(Original_array) and midpoint(true Original_array midpoint)
// subtracting I0 which is Low(Original_array)
// or here equals zero(0)
// so LC is quarter point in Original_array??
LC := I1 - I0;
// here we walk from begining of array
// and copy the elements between zero and LC
// this is funny call that Vals[i + I0] like 0 + 0
// then 1 + 0 and so on. I guess this guarantees if we are
// starting from non-zero based array??
for i := 0 to LC do
AVals[i]:=Vals[i + I0];
// k equal low(Original_array)
k := I0;
// I will be our zero based counter element
i := 0;
// J will be (midpoint + 1) or
// begining element of right side of array
j := J0;
// while we look at Copy_array elements
// between first element (low(Copy_array)
// and original_array from midpoint + 1 to high(Original_array)
// we start to sort it
while ((i <= LC) and (j <= J1)) do
// if the value at Copy_array is smaller than the Original_array
// we move it to begining of Original_array
// remember position K is first element
if (AVals[i] < Vals[j]) then begin
Vals[k] := AVals[i];
// move to next element in Copy_array
inc(i);
// move to next element in Original_array
inc(k);
// if the value at copy_array is larger
// then we move smaller value from J Original_array (J is midpoint+1)
// to position K original_array (K now is the lower part of ) Original_array)
end else if (AVals[i] > Vals[j]) then begin
Vals[k]:=Vals[j];
//move K to the next element in Original_array
inc(k);
// move j to next element in Original_array
inc(j);
// if the value in Original_array is equal to the element in Copy_array
// do nothing and count everything up
// so we end up with one copy from duplicate and disregard the rest
end else begin //duplicate
Vals[k] := AVals[i];
inc(i);
inc(j);
inc(k);
end;
//copy the rest
while i <= LC do begin
Vals[k] := AVals[i];
inc(i);
inc(k);
end;
// if the counters do not endup at the same element
// this means we have some that maybe leftover on
// the right side of the Original_array.
// This explains why K does not equal J : there are still elements left over
// then copy them to Original_array
// starting at position K.
if k <> j then
while j <= J1 do begin
Vals[k]:=Vals[j];
inc(k);
inc(j);
end;
// why K - 1?
// function needs result so return will be null if called
// I don't understand this part
Result := k - 1;
end;
//returns index of the last valid element
function PerformMergeSort(ALo, AHi:Integer): Integer; //returns
var
AMid, I1, J1:Integer;
begin
//It would be wise to use Insertion Sort when (AHi - ALo) is small (about 32-100)
if (ALo < AHi) then
begin
AMid:=(ALo + AHi) shr 1; // midpoint
I1 := PerformMergeSort(ALo, AMid); //recursive call I1 is a data point on the left
J1 := PerformMergeSort(AMid + 1, AHi); // recursive call I1 is a data point on the right
Result := Merge(ALo, I1, AMid + 1, J1);
end else
Result := ALo;
end;
begin
// test if array is even then we can split nicely down middle
if Length(Vals) mod 2 = 0 then
begin
SetLength(AVals, Length(Vals) shr 1);
Result := PerformMergeSort(0, High(Vals));
end
else
//array is odd let us add 1 to it and make it even
// shr 1 is essentially dividing by 2 but doing it on the bit level
begin
SetLength(AVals, (Length(Vals) + 1) shr 1);
Result := PerformMergeSort(0, High(Vals));
end;
end;
最佳答案
这是我对author提供的代码的修改，旨在在排序过程中删除重复项。一些解释：
外部功能：
我们应该提供缓冲区（aval）来存储初始aray的一半Length（Vals）div 2+1为奇偶数组提供了足够的空间，而不会造成不必要的复杂性更好的值（适用于所有情况）：长度（VAL+1）div 2
内部过程PerformMergeSort返回最后一个有效元素的索引，但外部过程返回有效元素的计数（在引用的主题中对其进行了注释），因此我使用（1+PerformMergeSort（））。
原因：在内部，我们必须处理索引，但此过程的最终用户应该知道新的数组长度。
内部功能执行排序：
它接受数组块的开始和结束索引，对该块排序并返回最后一个有效元素的索引在递归调用之后，我们会遇到这种情况。
不变：两个块都被排序，它们不包含重复项，左段的长度不为零
*****ACDEFG****BCDEGHILM******
^ ^ ^ ^
| | | |
Alo I1 AMid+1 J1
I0 I1 J0 J1 //as named in Merge
\____/
LC+1 elements
合并后：
*****ABCDEFGHILM**************
^ ^^
| ||__k
| |
Alo Result
内部功能合并：
使用提供的示例，笔和纸，逐步合并，看看它是如何工作的。
关于复制周期：我们将（lc+1）元素复制到临时缓冲区aval，使用aval的起始段（总是从0开始）和主数组的适当段（从i0开始，通常是非零的）。
关于algorithm - 剖析mergesort例程，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12733734/