同快速排序一样，也采用的是D&C的策略。时间复杂度也为O(nlogn)。

算法原理

归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并操作的过程

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置。
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾。

归并排序原理

1.将序列每相邻两个数字进行归并操作，形成个序列，排序后每个序列包含两个元素。
2.将上述序列再次归并，形成个序列，每个序列包含四个元素。
3.重复步骤2，直到所有元素排序完毕。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def MergeSort(arr):
    if len(arr) < 2:
        return arr
    return Merge(MergeSort(arr[:len(arr)/2]),MergeSort(arr[len(arr)/2:]))

def Merge(left,right):
    res = []
    left = sorted(left)
    right = sorted(right)

    while left and right:
        if left[0] < right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))
    return res + left +right

print MergeSort([6,5,2,3,4,1])

备注：思考一个问题，返回值为res + left +right，为什么不是res呢？注意，我们之前while循环的条件是left and right，实际上有很多情形下分布不均匀，导致left和right其中有一个为空的情况，因此我们需要把这种情况下，不为空的数组拼接起来。