归并排序算法

归并排序算法是在分治算法基础上设计出来的一种排序算法，它可以对指定序列完成升序（由小到大）或降序（由大到小）排序，对应的时间复杂度为O(nlogn)。

归并排序算法的思路是：

1) 将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；

2) 所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。

代码示例

1、子序列排序

例如：[14, 27, 35, 3, 10, 33]，先分成 [14, 27, 35] 和 [3, 10, 33] 两部分，从左往右依次取值比较大小，小的存储在临时变量中，再移动指针，直至一边先结束，将另一边剩下的元素直接追加到临时变量中。

def merge(arr, low, high, mid):
    i = low
    j = mid + 1
    temp = []
    while i <= mid and j <= high:
        if arr[i] < arr[j]:
            temp.append(arr[i])
            i += 1
        else:
            temp.append(arr[j])
            j += 1
    # 有一边先结束，剩下的元素元素直接追加
    while i <= mid:
        temp.append(arr[i])
        i += 1
    while j <= high:
        temp.append(arr[j])
        j += 1
    arr[low:high+1] = temp

# lst = [14, 27, 35, 3, 10, 33]
# merge(lst, 0, 5, 2)

2、递归调用

def merge_sort(arr, low, high):
    if low < high:
        mid = (low + high) // 2
        merge_sort(arr, low, mid)
        merge_sort(arr, mid + 1, high)
        merge(arr, low, high, mid)

lst = [27, 13, 35, 10, 3, 33]
merge_sort(lst, 0, 5)
print(lst)