マージソート

# アルゴリズムが正しく実装されていることを確認するために導入するカウンタ変数、ソート処理には関係がないことに注意
# 番兵は番兵(sentinel：センチネル！)は、プログラミングにおいて配列の最後に設置される特別な要素のことを指す。
# この要素は、通常の値と異なる値を持ち、配列の最後尾に置かれることが多い。
#left,rightの数値ってどこで決める？

count = 0

def merge(A, left, mid, right)
"""
    部分データ列 A[left] ~ A[mid-1], A[mid] ~ A[right-1] はそれぞれ整列済み
    2つの部分データ列をマージし、A[left] ~ A[right-1] を整列済みにする
"""
    # 2つの部分データ列のサイズ
    nl = mid-left
    nr = right-mid

    # 部分データ列をコピー
    for i in range(0,nl):
        L[i] = A[left+i]
    for i in range(0,nr):
        R[i] = A[mid+i]
    
    # 番兵ｰ>配列の最後に置く無限大を表す数字のこと。それぞれL,Rの配列の最後に置く
    # https://note.nkmk.me/python-inf-usage/
    L[nl] = [float('inf')]
    R[nr] = [float('inf')]
    
    # 2つの部分データ列をマージして A[left] ~ A[right-1] に書き込む
    lindex = 0
    rindex = 0

    for i in range(left,right):
        if L[lindex] < R[rindex]:
            A[i] = L[lindex]
            lindex++
        else:
            A[i] = R[rindex]
            rindex++
            count++


def merge_sort(A, left, right)
"""
    A[left] ~ A[right-1] をマージソートする
    配列 A をマージソートするには merge_sort(A, 0, n) を呼び出す
"""
    if left+1 < right:
        mid = (left + right) / 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


# 入力
n = int(input())
A = [int(x) for x in input().split()]

#left,rightの数値ってどこで決める？

ひとまずやり方はわかったのですが、
下の再帰関数のメソッドがわからず。
上にもある通り、まずそもそもleft,rightの数値をどこで決めるのか？
というところがわからず。
時間も時間になってしまったので、ギブして答えを見ました。

答えを見たあと説明を見ると
配列 A をマージソートするには merge_sort(A, 0, n) を呼び出す
ってこれかよ！って。
つまり最初のleftは0，rightはnですね。
つまり左端と右端の要素ってことだ。
でメソッドの中では配列を再帰で分割していっている。
最初は左、次は右。
で最後にマージ。

[float('inf')]は、とりあえず書き方はあるのだが、
別にこれはこう描かなくても、1000000001でもOK.
要するにありえない数値を書くってことで。

内容が理解できたところで、書き直し

count = 0
INF = 1000000001


def merge(a, left, mid, right):
    global count
    #結局lは左端から中央、rは中央から右端
    #でそのおしりに門番としてありえない数値をいれる

    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)

    # 2つの部分データ列をマージして A[left] ~ A[right-1] に書き込む
    lindex = 0
    rindex = 0

    for i in range(left, right):
        if l[lindex] < r[rindex]:
            a[i] = l[lindex]
            lindex += 1
        else:
            a[i] = r[rindex]
            rindex += 1
            count += 1


def merge_sort(a, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


n = int(input())
a = list(map(int, input().split()))

merge_sort(a, 0, n)

print(*a)
print(count)

以上。