问题
单项选择题
对n个记录的文件进行归并排序，所需要的辅助存储空间为( )。
A．O(1)
B．O(n)
C．O(log2n)
D．O(n2)
答案
参考答案：B
解析： 下表给出了主要排序方法的性能比较：
| 方法 | 平均时间 | 最坏情况时间 | 辅助存储 |
| 起泡排序、简单选择 排序、插入排序(除Shell排序) | O(n2) | O(n2) | O(1) |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) |
| 堆排序 | O(nlog2n) | O(nlog2 n) | O(1) |
| 归并排序 | O(nlog2n) | O(nlog2 n) | O(n) |