三、归并排序

将序列划分为两个子序列，分别对两个子序列递归进行归并排序，将这两个已排好序的子序列合并为一个有序序列。快速排序侧重于分割过程，归并排序侧重于归并过程。归并排序比快速排序多了一个归并过程，但快速排序的不足之处在于轴值的选择对算法效率的影响太大。归并排序避免了这种最差情况，不依赖于原始数组中记录的有序程度。