核心考点：#

• 时间复杂度：无论数组初始状态如何，均为 $O(n\log n)$，递归树深度为$\log_2n$，每层合并总操作次数为$O(n)$。
• 空间复杂度：$O(n)$，辅助数组的空间开销为核心，递归栈空间仅为$O(\log n)$。
• 稳定性：稳定排序，合并过程中相同元素的相对位置不会发生改变。
• 考研常考题型：递归实现代码编写、非递归实现思路、每一趟归并的结果推演、与快速排序/堆排序的复杂度&稳定性对比。

核心考点：#

• 时间复杂度：$O(d(n+r))$，其中$d$为关键字的位数，$r$为基数（如十进制排序$r=10$），$n$为元素个数。
• 空间复杂度：$O(n+r)$，需要$r$个辅助队列存储分配的元素，以及存储结果的辅助数组。
• 稳定性：稳定排序，分配和收集过程中保留相同位元素的原有顺序。
• 适用场景：数据范围已知且关键字位数固定的整数/字符串排序，不适用于需要比较整体大小的通用排序场景。

易混淆点：#

与归并排序的核心区别：基数排序不依赖元素间的比较，而是按位拆分处理，适合大批量低位数的整数排序。