排序算法之归并排序

最好时间复杂度为O(nlogn)
最坏时间复杂度为O(nlogn)

排序思想：
分：将数组中的元素分为两半，直到不能分则跳出
比：对于传入的两个数组进行比较
合：将输入的两个有序数组输出为一个有序数组
迭代：每次分比合的结果都要进行迭代，直到全部输出为止

代码 python
def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    else:
        mid = int(len(arr) / 2)
        left = MergeSort(arr[:mid])
        right = MergeSort(arr[mid:])
        return Merge(left,right)
def Merge(left,right):
    #将两个数组进行排序
    i,j = 0,0
    result = []
    while i < len(left) and j < len(right):
        if left[i] >= right[j]:
            result.append(right[j])
            j += 1
        else:
            result.append(left[i])
            i += 1
    result += left[i:]
    result += left[j:]
    return result