私はマージソートを学んでいて、マージステップで無限大としてセンチネルを使用していることに気づきました。
これがコーメンの本のアルゴリズムです。ステップ8と9で無限大を使用したのはなぜですか？
MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ← r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4 for i ← 1 to n1
5 do L[i ] ← A[ p + i − 1]
6 for j ← 1 to n2
7 do R[ j ] ← A[q + j ]
8 L[n1 + 1] ← ∞
9 R[n2 + 1] ← ∞
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i ] ≤ R[ j ]
14 then A[k] ← L[i ]
15 i ← i + 1
16 else A[k] ← R[ j ]
17 j ← j + 1
番兵はダミー値であり、そこにあるはずの値（ユーザー入力など）と制御値（特別に処理する必要のある値）を区別するために使用されます。1つの簡単な例は、リストの終わりをマークするためにnullからnullを使用することです。
この特定のケースでは、無限大を使用すると、リストの2つの半分がマージされるときに比較ロジックが簡略化されます（たとえば、無限大と比較して何かをマージする場合は少なくなるため、マージの終了の処理が簡略化されます）。 ）。
番兵の値は、有効な値ではあり得ない値にすぎません。
ドメインがゼロ以外の正の数値に制限されている場合、ゼロは番兵になる可能性があります。
ドメインが正の数に制限されていて、それ以外の場合は符号なし整数を使用する場合は、符号付き整数と負の数を番兵として使用できます。（もちろん、これを行うために、unsignedの範囲の上半分を失います。）
ポインタを使用して値を指す場合、nullポインタは番兵である可能性があります。
ポインター（またはポインターに減衰する配列）であるc文字列を使用している場合は、ヌルポインターを使用するか、場合によっては(char) 0（「空の文字列」）をポイントとしてセンチネルとして使用できます。 。
番兵は、有効な入力が決して引き受けられない値にすぎません。有効な値と間違えられないため、コードは番兵の値を検出したときに「何か特別なこと」を行うことができます。これは、有効な値に対して行う通常の処理とは異なります。
この場合、各再帰ステップで各サブ配列の最後に無限大（任意の数よりも大きい）を追加すると、次の場合に2つのサブ配列をマージするときに余分な比較が回避されます。
どちらの場合も、追加のコードの記述が終了した場合は、配列のいずれかが終了しているかどうかを確認するために、追加のロジックを記述する必要はありません。