基础练习——归并排序（非递归思考）

典型的分治，由于是平均分，所以时间复杂度是O(n²)。

递归

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    return merge(merge_sort(lst[:mid]), merge_sort(lst[mid:]))

def merge(lst_a, lst_b):
    lst = []
    i, j = 0, 0
    while i < len(lst_a) and j < len(lst_b):
        if lst_a[i] < lst_b[j]:
            lst.append(lst_a[i])
            i += 1
        else:
            lst.append(lst_b[j])
            j += 1
    return lst + lst_a[i:] + lst_b[j:]

非递归1

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    result = []

    stack = []
    mid = len(lst) // 2
    stack.append(lst[:mid])
    stack.append(lst[mid:])
    while stack:
        right = stack.pop()
        left = stack.pop()
        if len(left) > 1:
            mid = len(left) // 2
            stack.append(left[:mid])
            stack.append(left[mid:])
        else:
            result = merge(result, left)

        if len(right) > 1:
            mid = len(right) // 2
            stack.append(right[:mid])
            stack.append(right[mid:])
        else:
            result = merge(result, right)

    return result

但这个非递归版本只是使用堆栈代替递归，好繁琐，而且怪怪的，没有体现出两两合并，只是挨个合并，是不对的。

非递归2

def merge_sort(lst):
    parts = []
    for i in lst:               # 拆成一个一个的
        parts.append([i])

    i = 0
    while i < len(parts) - 1:
        result = merge(parts[i], parts[i + 1])
        parts.append(result)    # 两两合并好，追加到最后
        i += 2

    return parts[-1]            # 最后一个即是合并完整的

这个思路基本接近了，但是这个划分并不是递归版本的满二叉树分法，每次合并也不是同一层次的。比如[1, 2, 3, 4, 5]，这个版本是：

[1], [2] -> [1, 2]
[3], [4] -> [3, 4]
[5], [1, 2] -> [1, 2, 5]
[3, 4], [1, 2, 5] -> [1, 2, 3, 4, 5]

其实递归的顺序应该是：

[], [3] -> [3]; [4], [5] -> [4, 5]
[1], [2] -> [1, 2]; [3], [4, 5] -> [3, 4, 5]
[1, 2], [3, 4, 5] -> [1, 2, 3, 4, 5]

所以也不完全对。

非递归3

可不可以每次分的时候，记录当前的划分层次，完全重现递归版本的顺序呢？那估计需要构建一棵满二叉树，然后遍历解决。