c - 如何使用合并排序对外部排序中的运行进行排序

Question

我正在尝试(用 C 语言)使用合并排序来实现数据库的外部排序算法以完成大学作业。可用内存为 buffSize block 。我发现这个链接非常有帮助:

http://web.eecs.utk.edu/~huangj/CS302S04/notes/external-sorting2.html

但我的问题是关于算法第一阶段的伪代码的这一行:

使用内存中算法(如快速排序)对数组 a 进行排序

如果我无权使用 buffSize 空间以外的任何内存，因此无法分配链接的 a 数组，我该如何排序使用内存中排序过程(例如快速排序)来包含这些 block 中的记录(然后将它们存储在临时运行文件中)。在这种情况下，我的记录不会位于连续数组中，而是位于非连续内存块中，并且我无法直接应用 qsort。有什么提示吗？

Answer 1

外部排序的一般方法是:

1. 读取数组内存中能够容纳的尽可能多的数据。
2. 排序。
3. 将其写入临时文件(跟踪名称、大小以及最大记录等)。
4. 返回第 1 步，直到到达数据末尾。
5. 为写入的文件设置合并树，以便进行最少的合并。
6. 从每个第一个(唯一的？)合并阶段输入文件中读取一行。
7. 将最小的(升序排序)写入下一个临时文件(或最终文件)。
8. 获取一条新记录来替换刚刚写入的记录。
9. 返回第 7 步，直到没有更多数据可供读取。
10. 返回第 6 步继续合并，直至完成。

您还没有详细说明buffSize内存块的含义，但有一个可以在内存中排序的数组a。因此，您将数据读入数组。您可以使用快速排序对数组进行排序。然后将数组写入磁盘。重复读取、排序、写入，直到没有更多的输入数据。然后进行合并...