归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

• 时间复杂度O(N*logN)
• 空间复杂度O(N)
• 稳定排序

算法的原理如下：

归并排序首先是让待排序数据的每个数看为长度为1的有序区间，然后把相邻的两个长度为1的有序区间进行合并排序，得到长度为2的有序区间，然后再把相邻的有序区间进行合并，依次这么进行下去，2合4,4合8,8合16，直到所有的数合并成一个有序区间，数据就变的有序了。

Python实现

# 归并排序
def merge_sort