我一直在阅读The Art of Computer Programming，虽然它有一些我无法理解的高等数学，但做一些练习很有趣。
在我完成其中一个之后，我会去寻找答案，看看我是否比书中建议的更好或更差（通常更糟），但我不知道我目前的答案是什么试图传达。
本书的问题和建议的解决方案可以在这里找到
我所理解的是，这t可能是“缺失”元素的数量，也可能是一个一般常数，但我真正不明白的是看似任意的指令来根据它们的组件对它们进行排序，在我看来这就像在旋转你的轮子就位，因为乍一看它不会让你更接近原始订单。以及决定（除其他外）用数字替换成对名称的一部分（文件 G 包含 n−t < i ≤ n 的所有对 (i,xi)）。
所以我的问题很简单，如何从这个答案中提取算法？
一点澄清：
我明白它的目的是什么，以及我将如何将它翻译成 C++。我不明白为什么我应该对输入文件的副本进行排序，如果是这样，我应该按照哪些标准进行排序，以及将对的一侧更改为数字的原因。
假设名称是可排序的，并且有足够数量的磁带驱动器来解决问题。将一对定义为 (name, next_name)，其中 next_name 是向西的人的姓名。将成对文件的副本制作到另一个磁带上。第一个文件按名称排序，第二个文件按 next_name 排序。磁带排序是自下而上的归并排序或更复杂的变体，称为多相归并排序，但对于这个问题，标准的自下而上归并排序就足够了。对于 C++，您可以使用 std::stable_sort() 模拟磁带排序，使用 lambda 函数进行比较，第一个文件按名称排序，第二个文件按 next_name 排序。
索引术语使用 name[1] 表示最东端的名称，使用 name[n] 表示最西端的名称。
在对两个文件对进行初始排序后，解决方案指出“传递文件”是为了识别姓氏的下一个名称，name[n-1]，但没有指定如何。在此过程中，我假设 name[n] 也被识别。这些文件按顺序进行比较，将第一个文件中的名称与第二个文件中的 next_name 进行比较。不匹配表示名字，name[1] 或姓氏，name[n]，或者在极少数情况下，必须检查每个文件中的两者和下一个对以确定不匹配表示的内容。在识别姓氏 name[n] 时，第二个文件对中的 name 将是姓氏 name[n-1] 的下一个。
一旦知道 name[n-1] 和 name[n]，就会执行使用这两个文件的类似合并操作，跳过 name[n-1] 和 name[n] 以创建 F 对 (name[i], name[ i+2]) 对于 i = 1 到 n-2（按名称顺序），以及 G 有两对 (n-1, x[n-1]) 和 (n, x[n])，同样按名称顺序（G 和 G' 在最后一步之前按名称顺序排列）。
F被复制到H，并按照算法中的描述执行迭代过程，t每次加倍，2,4,8,...。每次通过后，F' 包含对 (x[i], x[i+t]) 为 i = 1 到 nt，然后将 G' 排序并与 G 合并回 G'，生成包含按名称顺序对 (i, x[i]) 表示 i = nt 到 n。最终，所有对都按名称顺序在 i = 1 到 n 的 G (i, x[i]) 中结束，然后 G 按索引（对的左侧部分）排序，从而产生按排序顺序的名称。