本文为 快速排序迭代版和递归版 的归并版本。
要点是 merge 的写法，同时支持迭代和递归
递归版：
def merge(S1, S2, result, result_start):
start, end1, end2 = 0, len(S1), len(S2)
x, y, z = start, start, result_start
while (x + y) < end1 + end2:
if (y == len(S2)) or (x < len(S1) and S1[x] <= S2[y]):
result[z] = S1[x]
x += 1
else:
result[z] = S2[y]
y += 1
z += 1
def merge_sort_recursive(S):
n = len(S)
if n < 2: return
mid = n // 2
S1, S2 = S[0:mid], S[mid:n]
merge_sort_recursive(S1)
merge_sort_recursive(S2)
merge(S1, S2, S, 0)
迭代版（同一 merge）
def merge_sort_iter(S):
n = len(S)
if n < 2: return
logn = math.ceil(math.log(n, 2))
src, dest = S, [None] * n
for i in (2**k for k in range(logn)):
for j in range(0, n, 2*i):
merge(src[j:j+i], src[j+i: min(j + 2 * i, len(src))], dest, j)
src, dest = dest, src
if S is not src:
S[0:n] = src[0:n]
其中 desc 和 src 的交换是作为空间复用。merge 函数 result_start 参数纯属为迭代函数准备。所以好的公共函数，有助于 迭代到递归的转化。
merge(src[j:j+i], src[j+i: min(j + 2 * i, len(src))], dest, j)
中 i 为 step， 一次比较几个元素， j 是这一轮 merge 的起点。
函数是不是确定实现了，没有没有其他 bug。 暂未详细研究。只是用了下面的代码来检验：
a = random.sample(range(30), 30)
merge_sort_iter(a)
assert a == list(range(30))
本着认真负责的态度，加强了验证。
from hypothesis import given, strategies as st
@given(st.lists(st.integers()))
def test_merge_sort_iter(numbers):
merge_sort_iter(numbers)
assert all(x <= y for x, y in zip(numbers, numbers[1:]))
说明算法基本上是正确的。 hypothesis 只是构建了部分输入集，并不能完全证明算法实现没有任何问题。但比普通单元测试靠谱。