为什么Merge Sort的Merge（）函数具有有条件的第二循环？

Question

merge1(int low, int high, int S[], U[]) 
{ 
    int k = (high - low + 1)/2
    for q (from low to high) U[q] = S[q]
    int j = low 
    int p = low 
    int i = low + k 

    while (j <= low + k - 1) and (i <= high) do 
    { 
        if ( U[j] <= U[i] ) 
        {
            S[p] := U[j] 
            j := j+1
        } 
        else 
        { 
            S[p] := U[i] 
            i := i+1 
        } 
        p := p+1 
    } 

    if (j <= low + k - 1) 
    { 
        for q from p to high do 
        { 
            S[q] := U[j] 
            j := j+1 
        } 
    }
}


merge_sort1(int low, int high, int S[], U[]) 
{ 
    if low < high 
    { 
        int k := (high - low + 1)/2 
        merge_sort1(low, low+k-1, S, U) 
        merge_sort1(low+k, high, S, U) 
        merge1(low, high, S, U) 
    } 
}

因此，基本上，这是在我的讲义上。我发现它一般而言令人困惑，但我了解其中最大的部分。我不明白的是需要“ if（j <= low + k -1）”部分。看起来它检查了左侧部分是否有“左”元素。合并时甚至可以吗？

Answer 1

合并两个排序列表时（我们打电话给他们 left 和 right），您不断使用一项并将其添加到 result 列表，直到您用完了任何一个 left 或者 right 列表。这是第一个 while 环形。现在，您需要将剩余元素添加到左或右列表中的元素中。有两个选择：

• 左列表不含元素，右列表仍然有一些。在这里编写代码的方式，我们不需要做任何事情，因为 S 数组已经包含了最后一个元素 right 列表。

• 右列表不含元素，左列表仍然有一些。然后，我们将其余元素复制到结尾 S. 。这就是 if 在......的最后 merge1 做。

---

关于您的问题，如果此代码为“不良”：代码是正确的，但是我会做一些更改以使其更可读：

• 描述性变量名称。
• 通过中点分开 left 和 right 列表到 merge1 而不是重新计算。