Python编程：排序算法之归并排序

归并排序

• 时间复杂度O(nlogn)
• 空间复杂度O(n)

假设现在的列表分两段有序，将其合成为一个有序列表

• 分解: 将列表越分越小，直至分成一个元素
• 一个元素是有序的
• 合并：将两个有序的列表合并，列表越来越大

代码实现

# 归并排序
import random
import sys
sys.setrecursionlimit(10000) # 设置递归深度默认1000

# 一次归并，合并有序序列
def merge(lst, low, mid, high):
    i = low
    j = mid + 1
    lst_temp = []
    while i