并归排序（Merge Sort）

又给自己出了一道题：用loop和recursive两种方式实现并归排序，Merge Sort，比较性能。

并归排序如果从上到下实现，就是典型的tree recursive，逻辑清晰。如果从下到上实现，就是采用loop方式，逻辑稍微复杂一点点。并归排序的时间复杂度是\(\Theta(N\log_2{N})\)，这是compare-based sorting算法的理论最优时间复杂度。

def merge_sort_recur(data: list[int]) -> list[int]:
    """ merge sort, recursive version """
    if (data_len:=len(data)) <= 1:
        return data

    midx = data_len // 2
    data_l = merge_sort_recur(data[:midx])
    data_r = merge_sort_recur(data[midx:])

    len_l = len(data_l)
    len_r = len(data_r)

    rtv = []
    i = j = 0
    while i<len_l and j<len_r:
        if data_l[i] < data_r[j]:
            rtv.append(data_l[i])
            i += 1
        else:
            rtv.append(data_r[j])
            j += 1

    if i == len_l:
        rtv += data_r[j:]
    else:
        rtv += data_l[i:]

    return rtv


def merge_sort_loop(data: list[int]) -> list[int]:
    """ merge sort, loop version """
    rtv = data[:]  # do not chage input data
    if (data_len:=len(rtv)) <= 1:
        return rtv

    s = 2
    while s < data_len*2:
        i = s // 2
        for j in range(0,data_len,s):
            t = []
            left, right = j, j+i
            while left<j+i and right<j+s and right<data_len:
                if rtv[left] < rtv[right]:
                    t.append(rtv[left])
                    left += 1
                else:
                    t.append(rtv[right])
                    right += 1
            if left == j+i:
                t += rtv[right:j+s]
            else:
                t += rtv[left:j+i]
            rtv[j:j+s] = t
        s *= 2

    return rtv


import random
data = [random.randint(0,int(1e4)) for i in range(int(1e4))]
sorted_data = sorted(data)
assert merge_sort_recur(data) == sorted_data
assert merge_sort_loop(data)  == sorted_data


import time
from timeit import timeit
n = 500
random.shuffle(data)
print('merge_sort_recur:',
      timeit('merge_sort_recur(data)',
             timer=time.process_time,
             number=n,
             globals=globals())/n)
print('merge_sort_loop:',
      timeit('merge_sort_loop(data)',
             timer=time.process_time,
             number=n,
             globals=globals())/n)
print('sorted:',
      timeit('sorted(data)',
             timer=time.process_time,
             number=n,
             globals=globals())/n)