2文件c++的双向合并排序

Question

我被要求对两个文件(记录文件)应用双向合并排序，算法解释步骤如下：

排序阶段1)要排序的文件上的记录分为几个组。每个组称为run，每次运行都适合主存。2)对每次运行应用内部排序，3)并将得到的排序运行分发到两个外部文件。 合并排序: 1)从在排序阶段创建的每个外部文件运行一次，合并成更大的排序记录运行。2)将结果存储在第三个文件中。3)将数据分发回前两个文件，并继续合并，直到所有记录都在一个大范围内运行。

我只能应用Sort Phase，所以当前的文件是：(假定运行仅包含3个键)

档案1: 50 95 110 x 40 120 153 档案2: 10 36 100 \ 60 70 130

以下是合并阶段的步骤，所以如果理论上解决这个问题，将执行以下操作：

合并阶段：

step1：

档案3: 10 36 50 95 100 110 40 60 70 120 130 153 x 22 80 140

档案1: 10 36 50 95 100 100 x 22 80 140

档案2: 40 60 70 120 130 153

步骤2：

档案3: 10 36 40 50 60 70 95 100 110 120 130 135 x 22 80 140

档案1: 10 36 40 50 60 70 95 100 110 120 130 135

档案2: 22 80 140

步骤3：

档案3: 10 22 36 40 50 60 70 80 95 110 120 130 135 140

一次运行停止排序完成

现在我需要应用合并阶段，以便每个文件中的每个键相互比较，并输出小到文件3，在步骤2中，将文件3重新分发到两个文件中，然后合并和排序，直到有一个排序运行。

如何在c++中应用这样的算法，我对如何确定每一步运行的大小感到有点困惑。

Answer 1

正如Amdt Jonasson所评论的那样，程序需要跟踪每个文件的运行大小和数据结束。在您的示例中，初始运行大小似乎是由3个元素组成的固定运行大小。合并两次大小为3的运行将导致一次6大小的运行，如您的步骤所示。在这种情况下，只需要跟踪每个文件中运行大小和数据结束的单个实例。

如果排序是一个稳定的排序(相同键上保留的原始顺序)，并且运行大小是可变的，那么每个文件都需要一个运行计数数组，或者以某种方式表示文件中运行的结束，例如文本文件，并使用一个特殊的字符序列作为运行指示符的结尾。

如果排序不需要是稳定的，则可以使用无序序列(在较大键值之后的较小键值)来指示运行的结束。这里的风险是，如果运行正常，两个或更多的运行似乎是一个单独的运行，这将失去稳定性和不平衡运行计数的文件。

这是一个双向合并排序使用3个文件。如果您使用第四个文件，那么每次合并运行都可以在两个输出文件之间交替，这样就不需要在每次合并通过之后对运行进行分割。

用3个文件进行双向合并排序的另一种方法是多阶段合并排序，但它很复杂，可能超出了类分配的预期，而且更像是一种“遗留”算法，可以追溯到基于磁带的排序中。