算法分析 ●对n个记录的文件进行归并排序,共需「log2n 趟,每趟所需比较关键字的次数不超过n,共比较 0(nlog2n)次。 ●每趙移动n个记录,共移动0(nlog2n)个记录。 ●归并排序需要一个大小为n的辅助空间y[1..n]。 归并排序是稳定的。算法分析 ● 对n个记录的文件进行归并排序,共需 log2n 趟,每趟所需比较关键字的次数不超过n, 共比较 O(nlog2n)次。 ● 每趟移动n个记录, 共移动O(nlog2n)个记录。 ● 归并排序需要一个大小为n的辅助空间y[1..n]。 ● 归并排序是稳定的