对于基本的排序算法，前面介绍了冒泡，选择，插入和希尔(增强版本的插入), 还有快速排序，现在还剩下最后一种基本的排序算法，那就是归并排序。归并排序像快速排序一样采用递归算法对列表进行分而治之，每次平均一分为二，分到只有一个元素为止。如果列表为空或只有一个元素时，那么从定义上来说它就是有序的; 当然归并排序的拆分最终不会有空列表的情况。拆分成一个个元素后再往回归并，归并是指将两个较小的有序列表归并为一个有序列表的过程。比如说两个单元素列表归并为两个元素的有序列表，两个双元素的列表归并为四个元素的有充列表，不断往上进行，最后形成一个有序的完整列表。

从维基百科的词条 Merge sort 找到下图，很深刻的描绘了归并排序的完整过程，红色箭头拆分，绿色箭头归并 Read More

前面说过最原始的复杂度为 O(n²) 的冒泡和选择排序，也跳跃到了复杂度为  O(n log n) 的快速排序，现在又再看一个复杂度同样为 O(n²) 的插入排序。从排序名称结合代码我们理解了为什么叫做冒泡或是选择，快速排序自认高名，那么何以这又谓之插入排序呢？是怎么插入，从左边往右边插，还是从右边往左边插，这得搞清它的排序原理：

它在列表较低的一端维护一个有序的子列表(从最左端一个元素开始)，并逐个将每个新元素(高端的)"插入"这个子列表。插入的时候遍历低端列表，找准位置插入便是，插入点后的元素需后移，当所有高端的元素插入完成了，整个列表就变得有序了。

整个排序操作示意图如下： Read More