1.归并排序

归并排序的基本思想是：将两个或两个以上的有序序列合并成一个新的有序序列。归并排序的基本步骤是：

（1）将n个记录的待排序序列看成是由n个长度为1的有序子表组成。

（2）将两两相临的子表归并为一个有序子表。

（3）重复上述步骤，直至归并为一个长度为n的有序表。

2.基数排序

基数排序(Radix Sorting)是和前面所述各类排序方法完全不相同的一种排序方法。从前面的讨论可见。实现排序主要是通过关键字间的比较和移动记录这两种操作，而实现基数排序不需要进行记录关键字间的比较。基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。

3.各种排序算法的比较

（1）平均的时间性能

时间复杂度为 O(nlogn)： 快速排序、堆排序和归并排序。

时间复杂度为 O(n²)： 直接插入排序、冒泡排序和简单选择排序。

当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n²) 。

简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 

（2）空间性能

这里指的是排序过程中所需的辅助空间大小。

所有的简单排序方法(包括：直接插入排序、冒泡排序和简单选择排序) 和堆排序的空间复杂度为O(1)；快速排序为O(logn)；归并排序所需辅助空间最多，其空间复杂度为 O(n)； 

（3）排序方法的稳定性能

直接插入排序、冒泡排序、归并排序和基数排序都是稳定的排序方法。

希尔排序、快速排序、简单选择排序和堆排序都是不稳定的排序方法。