1. 归并排序算法思想：

主要是使用了分治法的思想，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。

（1）分解成子问题

问题缩小到一定规模就更容易解决，归并排序的分解如下图所示：

（2）求解且合并

第一步排序且合并的过程如下： 合并到更高的层级： 直到最后一组，整个数据有序：

2. 以最后一步为例，详细解析：

如何把两个已经有序的子序列利用辅助空间合并为一个有序序列？ 蓝色箭头指向所选排序对象应放入的位置索引index，两红色箭头分别指向待排序子序列left 和right的对象索引。 （1）比较两待排序对象的健值大小，即比较2和1，显然1更小 （2）所以把1放入蓝箭头指向的位置，同时，索引index++，索引right++后，right指向4 （3）然后比较left索引和right索引指向的健值，即2和4… 重复此过程，直到两子序列合并完成。注意，有特殊情况，比如当left中所有元素已经全部合并，而right子序列还有元素没有放入，则把right所有元素直接放入辅助空间，不需要再比较了。

3. python代码实现归并排序如下：

class Solution(): def merge(self,leftArr,rightArr): auxArr = [] i = 0 j = 0 lenLeftArr = len(leftArr) lenRightArr = len(rightArr) while(i<lenLeftArr and j <lenRightArr): if(leftArr[i] < rightArr[j]): #找出更小的元素放进辅助空间 auxArr.append(leftArr[i]) i = i+1 else: auxArr.append(rightArr[j]) j = j+1 if(i == lenLeftArr): #当left中的元素已经全部合并时 for h in rightArr[j:]: auxArr.append(h) j = j + 1 if(j == lenRightArr): for k in leftArr[i:]: auxArr.append(k) i = i + 1 return auxArr def mergeSort(self,arr): if(len(arr)<=1): #注意递归停止的条件 return arr middle = int(len(arr)/2) left = self.mergeSort(arr[:middle]) right = self.mergeSort(arr[middle:]) return self.merge(left,right)

代码运行结果：

[1, 2, 3, 4, 5, 6, 7, 8]