# 配列Aの区間[l, m)の要素と区間[m, r)の要素をマージする
# それぞれの区間の要素は昇順に整列されている  
merge(A, l, m, r):
    for i ← l to r-1:
        T[i] ← A[i]

    reverse(T, m, r)

    i ← l
    j ← r-1

    for k ← l to r-1:
        if T[i] ≤ T[j]:
            A[k] ← T[i]
            i ← i + 1
        else:
            A[k] ← T[j]
            j ← j - 1


# 配列全体について、前半・後半に分けてマージする場合の使用例
merge(A, 0, N/2, N)