难以理解合并排序算法的合并部分

Question

我在理解合并排序算法的“合并”部分时有点困难，因为我试图在上下文中理解算法的部分，而某些变量/循环对我来说没有意义。我理解递归除法过程和合并的排序方面，但在这个特定的合并算法中：

    public static void merge(int data[], int temp[], int low, int middle, int high){
    int ri=0; //result index
    int ti=low;//temp index
    int di=middle;//data index
    int[] result = new int[high-low+1];

    while (ti<middle && di<=high){
      if (data[di]<temp[ti]){
        result[ri++] = data[di++];//smaller is in data
       } 
       else{
            result[ri++] = temp[ti++];//smaller is in temp
            }
    } 

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

我不明白最后3个循环：

while(ti<middle) result[ri++]=temp[ti++];
while(di<=high) result[ri++]=data[di++];
for(int i=0;i<high;i++) data[low+i]=result[i];

你能解释一下这3个循环在合并的上下文中是用来做什么的吗？还有什么进一步的建议可以帮助你更好地理解合并排序算法的合并部分吗？

Answer 1

这个循环的条件while（ti

while(ti<middle) result[ri++]=temp[ti++]; // Remaining elements from the first half.
while(di<=high) result[ri++]=data[di++]; // Remaining elements from the second half.

现在我们需要将合并的结果复制到原始数组。这正是最后一行所做的。

关于对合并阶段的理解：你理解算法本身吗（在数学意义上，不参考任何具体的编程语言）？如果你不知道，那就先试着不看任何代码就完全理解它。如果你确实理解了算法，但不理解这段代码，没关系，因为这段代码很糟糕。

您可以查看一个更清晰的实现：

mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = 
    let (firstHalf, secondHalf) = splitAt (length xs `div` 2) xs
    in merge (mergeSort firstHalf) (mergeSort secondHalf)  

merge xs [] = xs
merge [] ys = ys
merge xs@(x:xt) ys@(y:yt) 
    | x <= y = x : merge xt ys
    | otherwise = y : merge xs yt