我正在从Elmasri和Navathe的作者，第5版的数据库系统基础一书中研究数据库，并且几乎在第15章开始时，他们都使用合并排序简要地解释了外部排序。他们将算法分为两个阶段：
1）排序：他们使用下一个符号：
在此阶段中，我们将尽可能多的块放入数据文件中，使用任何内部排序算法对它们进行排序，并将它们写入为临时排序的子文件。我们在文件的其余块中重复此操作，因此我们将获得更多排序的子文件。这些子文件被它们称为“部分”，它们的数量是：
nr =？b / nb？。
符号？？表示上限功能。此阶段的I / O成本为2b，因为我们需要一次读取每个块（b次访问）。然后，要保存所有部分，我们还需要进行b访问。
2）合并：他们说类似的话（我用我的解释重写了它，以使其更清楚）：
生成的部分（有序子文件）以一遍或多遍混合。每次通过时，将在内存中保留一个输出块，以放置混合结果，其余部分用作输入块，最大可达nb-1，并且每个块一次放置一个块有序部分，目的是将它们混合。当输入块少于部分时，需要多次通过。另外，由于每个部分可以具有一个以上的块，因此将每个遍细分为迭代，每个迭代中都放置了每个部分的块。
数字dm必须等于（nb-1）和nr之间的最小值。如果我们将对数的底数放在（）之间，而其对数放在??之间，则通过的次数为：
？log（dm）？nr ??。
我感到困惑的部分是，他们说这一阶段的成本是
2b *？log（dm）？nr ??，
所以他们基本上是在暗示，在每遍中，我们只需要读取一次每个块并将其写入一次，但是我不确定这是否正确。我怀疑可能需要更多访问权限。
因此，该算法的总成本为2b + 2b *？log（dm）？nr ??。
= 2b（1 +？log（dm）？nr ??）
实际上，他们不是这样说的，而是：“通常，对数以dm为底，表示访问的块数的表达式如下：”
（2 * b）+（2 *（b *（log（dm）？nr？））），
基本上是一样的
例如，假设我们有一个10个块的文件，每个块3条记录。内存（缓冲池）中的可用空间为4个块。让我们用||分隔文件的块
29,11,27 || 22,1,20 || 7,30,26 || 9,8,21 || 13,24,15 || 23,4,28 || 17,12,10 || 5,3,6 || 16,19,2 || 25,14,18
导致分选阶段的部分“ nr”的数量为“ …