问如何优化合并排序？

EN

因为你只做了一个合并，而不是一个完整的排序，所以它只是一个基本的合并循环。纯粹的顺序I/O。不需要担心缓冲区。想象一下夹克上的拉链。就这么简单。(注意:如果文件中的数字是二进制格式，速度可能会快得多。不仅文件会更小，而且程序的I/O也会受到限制，而且数字也会非常准确。)

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

在回答您的问题时，考虑一个更简单的问题，将一个文件复制到另一个文件。您只需要执行顺序I/O，而这正是文件系统所擅长的。您可以编写一个简单的循环，从文件中读取字节或整数等小单元，并将其写入其他单元。只要你尝试读取一个字节，系统就会分配一个很大的缓冲区，将文件的一大块刷到缓冲区中，然后将该字节从缓冲区中提供给你。它一直这样做，直到你需要另一个缓冲区，当它隐形地为你扫视另一个缓冲区时。同样的事情也会发生在你正在编写的文件中。现在CPU速度很快，所以它可以遍历输入字节，将它们复制到输出，所需时间只有读取或写入缓冲区的时间的一小部分，因为读取或写入不能比外部硬件更快。更大的缓冲区会有帮助的唯一原因是，读/写时间的一部分是所谓的“延迟”，基本上是将磁头移动到所需磁道并等待所需扇区出现所需的时间。大多数文件系统将文件分解为分散在磁盘周围的块，因此磁头无论如何都是跳跃的。你可以听到它。

复制和像您的合并算法之间的唯一区别是它读取两个文件，而不是一个文件。无论采用哪种方式，基本的时序都是一系列的缓冲区读写操作，其间夹杂着少量的CPU操作。(可以进行重叠I/O，因此CPU操作在I/O发生时发生，因此缓冲区读取和写入之间基本上没有延迟，但当CPU速度慢1000倍时，延迟会更大。)

当然，如果您可以将其安排为正在读取和写入的文件都位于不同的物理磁盘驱动器上，并且这些驱动器不会有太多碎片，那么磁头移动量就可以降到最低，而更大的缓冲区可能会有所帮助。但基本上，使用一个简单的程序，您可以很好地预期简单的代码会像磁盘移动数据一样快，而巨大的缓冲区可能会有所帮助，但不会有太大帮助。