Merge SurtのMerge（）関数に条件付き2番目のループがあるのはなぜですか？

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

2つのソートされたリストをマージするとき（それらを呼び出しましょう left と right）、あなたは1つのアイテムを取り続け、それをに追加し続けます result リスト、どちらかのアイテムがなくなるまで left また right リスト。これは最初に行われます while ループ。次に、左または右のリストに残りの要素を結果リストに追加する必要があります。 2つのオプションがあります。

• 左のリストには要素がなく、適切なリストにはまだいくつかあります。コードがここに書かれている方法は、終了してから何もする必要はありません。 S 配列には、の最後の要素が既に含まれています right リスト。

• 右のリストには要素がなく、左のリストにはまだいくつかあります。次に、残りの要素を終了までコピーします S. 。これが何であるかです if の終わりに merge1 します。

---

このコードが「悪い」かどうかについての質問について：コードは正しいですが、私はそれをより読みやすくするためにいくつかの変更を加えます：

• 記述変数名。
• 分離する中間点を通過します left と right のリスト merge1 再計算する代わりに。