算法技术手册（原书第2 版）

排序算法

｜

83

排序算法

4.8.4 算法分析

在使用递归排序算法对

A

[

start

,

end

)

左半部分和右半部分排序之后，

归并排序

会在

O(

n

)

的时间内完成“归并”阶段，将排完序的元素正确地放入数组中，并将该数组作为返回

结果。

copy

原封不动地复制了整个数组

A

，所以在副本中，所有元素都在原有位置上，递归必

定会达到结束条件。观察到这一点比较复杂，同时也是这个算法的关键。此外，最终的

归并步骤只需要

O

(

n

)

次操作，这确保了总体性能依旧是

O

(

n

log

n

)

。由于

copy

是算法唯

一使用的额外空间，因此总的空间需求为

O

(

n

)

。

4.8.5 衍生算法

在所有排序算法中，

归并排序

是最容易转换为处理外存数据（例如磁盘）的算法。例

4-11

为一个完整的

Java

实现，该实现使用了内存映射数据来高效地完成对包含二进制编

码的整数文件的排序。不过该算法要求元素都具有相同的大小，因此无法适用于任意字

符串或者其他变长元素的排序。

例

4-11

：外部归并排序的

Java

实现

public static void mergesort (File A) throws IOException {

File copy = File.createTempFile ("Mergesort", ".bin");

copyFile(A, copy);

RandomAccessFile src = new RandomAccessFile (A, "rw");

RandomAccessFile dest = new RandomAccessFile ...