归并排序
归并排序是用到了分治的思想，分治的思想是将一个大问题拆分成很多的小问题，然后再将已经处理完成的小问题合并成整个的大问题。
归并排序首先将数组等分，然后排序等分后的数组，最后再将排好序的两个数组合并成一个排好序的数组。归并排序的时间复杂度是O(n log n)
为了能够更好的理解归并排序，我们来看下面的数组：
依然是上次我们用到的没有排序的数组，上面总共有八个数字，等分后就会变成每组四个数字。这样的等分一直持续到只剩下一个数字的情况。
由于还没有将数组等分到只有一个元素的情况，所以我们继续等分。
此时，每个分组中只有两个数字，还是可以继续等分。
在这个时候，等分结束。因为所有的分组都只能分到这种程度，没有数组还能继续等分了。
然后我们将数组进行俩俩合并，首先我们需要比较两个数组中的每一个数据，然后将这些数据放入一个新的数组中，新数组就是有序的。这里比较的过程就是 14 和 33 是升序的，不需改变。27 和 10 是降序的，需要先放入10，再放入27. 35 和19也是降序的，需要先放入19， 再放入27. 最后，42 和 44 是升序的，不需改变。
再下一次将前两个合并到一个数组中，后面两个合并到一个数组中。过程是：前两个数组合并，先判断14 和 10，发现 14 要 大于10，所以在新生成的数组中将 10 写在第一个位置上。然后比较14 和 27 发现14小，将 14 写在新生成的数组的第二个位置。在比较33 和 27，发现27 小，将27写在新生成的数组中。由于第二个数组写入完成，所以将第一个数组的剩余部分写入新生成的数组。第三组和第四组合并过程也是类似：19 vs. 42 => 19, 35 vs. 42 => 35, 一个结束另一个写入剩余的部分=>42, 44
最后，经过最终的merge操作，生成的数组就是下面的这个模样：
代码示例
def MergeSort(array):
arrayLen = len(array)
# 如果长度小于等于1，就返回array即可
if arrayLen <= 1:
return array
# 取中间值
middleNum = arrayLen >> 1
# 左边的部分去做MergeSort
leftArray = MergeSort(array[:middleNum])
# 右边的部分去做MergeSort
rightArray = MergeSort(array[middleNum:])
# 将左右两边合并，成为一个新的数组，并已经排序成功
return MergeCore(leftArray, rightArray)
def MergeCore(leftArray, rightArray):
# 首先需要定义两个指针，这两个指针分别指向两个数组的第一个元素
leftPointer, rightPointer = 0, 0
# 定义一个返回列表(这一步就代表控件复杂度至少是O(n))
retArray = []
leftLen = len(leftArray)
rightLen = len(rightArray)
# 循环两个数组，循环最小值加入到返回值得数组中
while leftPointer < leftLen and rightPointer <rightLen :
if leftArray[leftPointer] < rightArray[rightPointer]:
retArray.append(leftArray[leftPointer])
leftPointer += 1
else:
retArray.append(rightArray[rightPointer])
rightPointer += 1
# 下面的代码是将剩余的数组中的内容放置到返回的数组中
retArray += leftArray[leftPointer:]
retArray += rightArray[rightPointer:]
return retArray
if __name__ == '__main__':
testList = [2,7,6,1,5,4,9,3]
print(MergeSort(testList))
