8.5 归并排序、基数排序·选择题讲评

归并比较排序、稳定；基数和计数是非比较排序，性能依赖键域。

手工推演与代码

比较排序下界适用于基于比较的一般排序，不限制计数排序在小整数域达到线性。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。用nlogn下界否定计数排序；基数每趟不稳定；归并空间写递归深度。

迁移训练

小值域整数大量重复优先考虑什么？答案计数排序。