kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_5_B: Merge Sort

擬似コードをそのまま書けばほとんど終わりだけどあえてイテレータで書いてみた
こういう書き方で合ってるんだろうか
若干無理してる感あるような気も

 

#! /usr/local/bin/python3
# coding: utf-8

from math import inf

c = 0

def merge(A, left, mid, right):
    global c

    L = A[left:mid]; L.append(inf)
    R = A[mid:right]; R.append(inf)
    i = iter(L); l = next(i)
    j = iter(R); r = next(j)
    for k in range(left, right):
        c += 1
        if l <= r:
            A[k] = l
            l = next(i)
        else:
            A[k] = r
            r = next(j)

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)

def main():
    n = int(input())
    S = [int(x) for x in input().split()]
    merge_sort(S, 0, n)
    print(*S)
    print(c)

main()

比較回数はグローバル変数にしてしまったけどなにかかっこいい書き方ないかな