我正在学习归并排序，在归并步骤中偶然发现使用哨兵作为无穷大。
这是Cormen的书中的算法。为什么我们在第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
哨兵是一个虚拟值，用于区分应该存在的值(例如用户输入)和控制值(需要特殊处理的值)。一个简单的例子是使用null到null来标记列表的结束。
在这种特殊情况下，当列表的两半被合并在一起时，使用无穷大简化了比较逻辑(例如，当合并任何与无穷大相比的东西时，将会更少，因此合并结束的处理被简化)。
前哨值只是一个没有有效值的值。
如果我的定义域被限制为正的非零数，0可以是一个哨兵。
如果我的域仅限于正数，否则我将使用无符号整数，我可以使用有符号整数和负数作为哨兵。(当然，为了做到这一点，我失去了unsigned范围的上半部分)
如果我使用指针指向一个值，空指针可以作为哨兵。
如果我使用的是c-string，它是一个指针(或衰变成指针的数组)，我可以使用空指针，或者在某些情况下，指向(char) 0("空字符串")作为哨兵。
哨兵只是一个值，是你的有效输入永远不能取的。因为它不会被误认为是一个有效值，所以当看到哨兵值时，代码可以做一些"特殊的事情"，而不是对有效值所做的正常处理。
在这种情况下，在每个递归步骤中向每个子数组的末尾添加无穷大(大于任何数字)，将避免在合并两个子数组时在以下情况下进行额外的比较
- 当第一个数组结束，第二个数组还在时
- 或者当第二个数组结束而第一个数组仍在时
在这两种情况下都不需要编写额外的逻辑来检查数组是否结束，如果结束了编写一些额外的代码。