マージソート

def merge(a, b):
    i, j, res = 0, 0, []                # a と b のインデックス、および結果を格納する配列
    while i < len(a) or j < len(b):     # まだ要素が残っている間
        ai = a[i] if i < len(a) else float('inf')
        bj = b[j] if j < len(b) else float('inf')

        if ai < bj:                     # a[i] < b[j] の場合は a[i] を採用
            res.append(ai)              # 結果に a[i] を追加
            i += 1                      # 次の要素へ
        else:                           # a[i] >= b[j] の場合は b[j] を採用
            res.append(bj)              # 結果に b[j] を追加
            j += 1                      # 次の要素へ
    return res


def merge_sort(a):
    if len(a) <= 1:                     # ソートする要素がないとき
        return a                        # 配列をそのまま返す

    l = merge_sort(a[: len(a) // 2])    # 左側をソート
    r = merge_sort(a[len(a) // 2:])     # 右側をソート
    return merge(l, r)