归并排序

归并排序采用分治的思想，通过不断的将数组一分为二，直到不可再分，然后对已排序的子数组递归合并，最后使得整个数组有序，归并排序的最好、最坏以及平均时间复杂度都是O(NlogN)。

算法的主要思路是

1. 选取数组中间位置，将数组分为两个子数组。
2. 继续对两个子数组执行1～2步操作，直到子数组中只有一个元素。
3. 递归合并有序的子数组。

下面是数组[6, 5, 12, 10, 9, 1]使用归并排序算法进行排序的过程。

归并排序算法实现

归并排序虽然在数组排序上效率低于快速排序，但是对链表进行排序时，归并排序通常是最佳选择，因为链表无法通过索引访问，如果使用快速排序效率会低很多，而归并排序对随机访问依赖较小，所以能够高效的完成链表的排序。

另外由于归并排序在排序过程中，左右子数组的排序并无依赖关系，所以可以并行提高效率。

下面是使用归并排序算法对链表进行排序的实现。