8.5 归并排序和基数排序
8.5.1 归并排序
多个有序表合成一个有序表。
比较次数数量级与初始状态无关。
8.5.2 基数排序
长度为 n 的线性表排序。
高位优先（MSD）：从高位到低位分配和收集。
低位优先（LSD）：从低位到高位分配和收集。
辅助队列空间 r(r 个队列：r 个队头指针和 r 个队尾指针)，r 为基数。
d 趟分配和收集，一趟分配需要 $O(n)$，一趟收集需要 $O(r)$。
时间复杂度 $O(d(n+r))$。
元素移动次数与关键字初始排列次序无关。
多个有序表合成一个有序表。
比较次数数量级与初始状态无关。
长度为 n 的线性表排序。
高位优先（MSD）：从高位到低位分配和收集。
低位优先（LSD）：从低位到高位分配和收集。
辅助队列空间 r(r 个队列：r 个队头指针和 r 个队尾指针)，r 为基数。
d 趟分配和收集，一趟分配需要 $O(n)$，一趟收集需要 $O(r)$。
时间复杂度 $O(d(n+r))$。
元素移动次数与关键字初始排列次序无关。