jro*_*028 2 sorting algorithm mergesort
我目前正在上我的第一门算法课，我们最近开始谈论归并排序。我们的教授向我们展示了带有标记值的归并排序的伪代码，但并没有真正解释它们的目的。我仍然对它们的用途感到困惑，因为我们的家庭作业之一是编写没有哨兵值的合并排序。包含哨兵值有什么优点或缺点吗？任何帮助将不胜感激。
编辑：请注意，我之前已经编写了一个合并排序程序，并且在没有标记值的情况下这样做了，这是导致我困惑的部分原因。
小智 5
在归并排序中使用哨兵可以防止我们需要检查是否已经到达正在排序的数组的末尾。可以在没有哨兵的情况下执行合并排序，但是没有哨兵的合并排序的实现会为比较循环的每次迭代添加额外的检查。
例如：
我将按照 Cormen、Leiserson、Rivest 和 Stein 的算法介绍和分析中的描述来描述它，使用两叠扑克牌来表示要排序的两个数组。
我们假设两堆卡片都是正面朝上的，并按照每堆中最小的卡片在顶部，每堆中最大的卡片在底部进行排序。
让我们将左侧的纸牌阵列称为“L”，将右侧的纸牌阵列称为“R”。
对于合并排序的每次迭代，我们将比较每堆中最上面的卡片，并确定哪一个是最小的。我们将从堆中取出最小的卡片，并将其面朝下放置以创建一组新的排序卡片。这是归并排序的首要原则。
但是，在我们对每一堆最上面的牌进行比较之前，我们必须确保每一堆上都有一张牌。例如，如果左侧堆中的牌始终小于右侧堆中的牌，我们可以在接触右侧堆中的任何一张牌之前用尽左侧堆中的牌。在我们的代码中，这意味着当我们继续尝试查看数组中的下一项时，我们最终会尝试访问不存在的数组索引，因为我们已经查看了该数组的所有索引值。为了避免这种情况发生，我们需要在合并排序中的每个比较之前进行检查，以确保每个数组中仍有一个值进行比较。
使用哨兵可以防止我们在每次比较之前执行这种额外的检查，确保我们永远无法从一个或另一个堆中取出所有卡片。如果我们使用 'infinity' 作为标记值，那么 'infinity' 卡将永远不会从堆中移除，因为没有任何值会大于 'infinity'。这确保了数组中总是有一个值可以进行比较。
想想上面的例子：左边一堆的牌总是比右边一堆的牌小。左侧堆中的卡片将一次移除一张，直到达到“无限”（哨兵）卡片为止。然后，正确堆中的牌将开始耗尽。
在某些时候，两堆都会在上面放上他们的“无限”牌。但是，此时，循环计数器将达到其最大值，导致循环在尝试访问不存在的数组索引之前终止。