Problem:


Merge Sort

Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.

Merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  create array L[0...n1], R[0...n2]
  for i = 0 to n1-1
    do L[i] = A[left + i]
  for i = 0 to n2-1
    do R[i] = A[mid + i]
  L[n1] = SENTINEL
  R[n2] = SENTINEL
  i = 0;
  j = 0;
  for k = left to right-1
    if L[i] n is given. In the second line, n integers are given. 

Output

In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Constraints

n ≤ 500000

0 ≤ an element in S ≤ 109

Sample Input 1

10
8 5 9 2 6 3 7 1 10 4

Sample Output 1

1 2 3 4 5 6 7 8 9 10
34

Notes

Template in C
-->



Sample input:
10
8 5 9 2 6 3 7 1 10 4


Sample output:
1 2 3 4 5 6 7 8 9 10
34

Submission status: Accepted

Solution code:
count = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = A[left: left + n1], A[mid: mid + n2]

    L.append(2000000000)
    R.append(2000000000)

    i, j = 0, 0
    for k in range(left, right):
        global count
        count += 1
        #print("k", k, "l", left, "m", mid, "r", right, "L", L, "R", R)
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    #print("l", left, "r", right)
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
input_list = list(map(int, input().split(' ')))

mergeSort(input_list, 0, n)

print(*input_list)
print(count)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    l, r = [], []
    for i in range(left, mid):
        l.append(a[i])
    l.append(float('inf'))
    for i in range(mid, right):
        r.append(a[i])
    r.append(float('inf'))
    i, j = 0, 0
    for k in range(left, right):
        if l[i] < r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1


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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = merge_sort(a, 0, len(a))
    print(' '.join(map(str, a)))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    l = a[left:mid]
    r = a[mid:right]
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 0

    for k in range(left, right):
        ans += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
    
    return ans


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


def print_list_split_whitespace(s):
    for x in s[:-1]:
        print(x, end=" ")
    print(s[-1])

n = int(input())
s = [int(x) for x in input().split()]

ans = merge_sort(s, 0, len(s))

print_list_split_whitespace(s)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, maxsize


def stdinput():
    return stdin.readline().strip()

def main():
    n = int(stdinput())
    *A, = map(int, stdinput().split(' '))
    o = mergeSort(A, 0, n)

    print(*A)
    print(o)

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]

    cap = maxsize
    L.append(cap)
    R.append(cap)

    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return i + j

def mergeSort(A, left, right):
    o = 0
    if left + 1 < right:
        mid = (left + right) // 2
        o += mergeSort(A, left, mid)
        o += mergeSort(A, mid, right)
        o +=  merge(A, left, mid, right)
    return o

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
count = 0

def main():
    mergeSort(s, 0, n)
    print(' '.join(map(str, s)))
    print(count)

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

def merge(a, left, mid, right):
    global count
    l = a[left:mid]
    r = a[mid:right]
    i = 0
    j = 0
    l.append(float('inf'))
    r.append(float('inf'))
    for k in range(left, right, 1):
        if l[i] < r[j]:
            a[k] = l[i]
            i += 1
        else :
            a[k] = r[j]
            j += 1
        count += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    while xp < c:
        while xp < c and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
#                print x[xp:c], R[rp:right-mid]
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                    rp += 1
                break
        while xp < c and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
#                print x[xp:c], L[lp:mid-left]
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                    lp += 1
                break
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    while xp < c:
        while xp < c and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
#                    rp += 1
                break
        while xp < c and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
#                    lp += 1
                break
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    while xp < c:
        while xp < c and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                break
        while xp < c and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                break
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while xp < c and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
                break
        while xp < c and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
                break
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True

    def f(A,xp):
        for e in A:
            x[xp] = e
            xp += 1
        return False
    
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                flg = f(R[rp:], xp)
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                flg = f(L[lp:],xp)
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = int(raw_input())
S = map(int, raw_input().split())

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin

num_swap = 0


def merge(a, left, mid, right):
    global num_swap
    L = a[left:mid]
    R = a[mid:right]
    L.append(10**9+1)
    R.append(10**9+1)
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
        num_swap += 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)


stdin.readline()
s = [int(s) for s in stdin.readline().split()]
merge_sort(s, 0, len(s))
print(*s)
print(num_swap)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = a[left:left + n1] + [SENTINEL]
    R = a[mid:mid + n2] + [SENTINEL]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    count += right - left

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)

SENTINEL = 1000000001
n = int(input())
a = list(map(int, input().strip().split()))
count = 0
merge_sort(a, 0, len(a))
print(' '.join(map(str, a)))
print(count)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [10000000000]
    R = A[mid:right] + [10000000000]

    i = j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1

        else:
            A[k] = R[j]
            j += 1

        cnt += 1

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


n = int(input())
lst = list(map(int, input().split()))
cnt = 0

mergeSort(lst, 0, n)
print(*lst)
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
L = [int(x) for x in input().split()]
cnt = 0

def Merge(S, l, m, r):
    global cnt
    cnt += r - l
    L = S[l:m] + [float('inf')]
    R = S[m:r] + [float('inf')]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] < R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1
    return

def MergeSort(S, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(S, l, m)
        MergeSort(S, m, r)
        Merge(S, l, m, r)
    return

MergeSort(L, 0, n)
print(*L)
print(cnt)

Submission status: Accepted

Solution code:
N_MAX = 1000000000

n = int(input())
S = list(map(int, input().rstrip().split(" ")))

mergeCnt = 0

def merge(A, left, mid, right):
    
    global mergeCnt
    
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid]
    R = A[mid:right]
    
    L.append(N_MAX)
    R.append(N_MAX)
    
    i = j = 0
    
    for k in range(left, right):
        mergeCnt += 1
        if(L[i] <= R[j]):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

if(__name__ == '__main__'):
    
    left = 0
    right = n
    
    mergeSort(S, left,right)
    
    print(*S)
    print(mergeCnt)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int,input().split()))

def marge(l,r):
    count = 0
    conq = []
    i = 0
    j = 0
    k = len(l) + len(r)
    l.append(float('inf'))
    r.append(float('inf'))
    for o in range(k):
        if l[i] <= r[j]:
            conq.append(l[i])
            i += 1
        else:
            conq.append(r[j])
            j += 1
        count += 1
    return conq,count
           
def margeSort(s):
    n = len(s)
    if n == 1:
        return s,0
    else:
        L, cnt_L = margeSort(s[:n//2])
        R,cnt_R = margeSort(s[n//2:])
        s,cnt = marge(L,R)         
    return s,cnt+cnt_R+cnt_L
S,count = margeSort(S)
print(*S)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
S = [*map(int, input().split())]

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = list(range(n1+1))
    R = list(range(n2+1))
    
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
        
    L[n1] = 100000000000
    R[n2] = 100000000000
    
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i = i + 1
            
        else:
            A[k] = R[j]
            j = j + 1
            
    return right - left
            
def mergeSort(A, left, right):
    count = 0
    if left+1 < right:
        mid = int((left + right) / 2)
        count += mergeSort(A, left, mid) + mergeSort(A, mid, right)
        count += merge(A, left, mid, right)

    return count

count = mergeSort(S, 0, n)
print(*S)
print(count)

Submission status: Accepted

Solution code:
def merge(A,left, mid, right):
    global cnt
    L = A[left:mid] + [1000000001]
    R = A[mid:right] + [1000000001]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1 
        else:
            A[k] = R[j]
            j += 1
    cnt += right - left

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

if __name__ == '__main__':
    n = int(input())
    A = list(map(int,input().split()))
    cnt = 0
    mergeSort(A, 0, n)
    print(*A)
    print(cnt)

Submission status: Accepted

Solution code:
def merge(a,left,mid,right):
    count=0
    L=a[left:mid]+[float("inf")]
    R=a[mid:right]+[float("inf")]
    i,j=0,0
    for k in range(left,right):
        count+=1
        if L[i]<=R[j]:
            a[k]=L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
    return count

def mergeSort(a,left,right):
    if left+1<right:
        mid=(left+right)//2
        countl=mergeSort(a,left,mid)
        countr=mergeSort(a,mid,right)
        return merge(a,left,mid,right)+countl+countr
    return 0



n=int(input())
a=list(map(int,input().split()))
ans=mergeSort(a,0,n)
print(" ".join(map(str,a)))
print(ans)

Submission status: Accepted

Solution code:
count = 0


def main():
    input()
    A = [int(x) for x in list(input().split())]
    merge_sort(A, 0, len(A))
    print(*A)
    print(count)


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 merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid

    # リストの左側を作成
    L = A[left:mid]

    # リストの右側を作成
    R = A[mid:right]

    # 終端追加
    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
num = int(input())
arr = list(map(int, input().split()))

def merge(arr, left, middle, right, count):
    L = arr[left:middle]
    L.append(float('inf'))
    R = arr[middle:right]
    R.append(float('inf'))

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        count += 1
        if l <= r:
            arr[index] = l
            l = next(iterL)
        else:
            arr[index] = r
            r = next(iterR)
    return count

def merge_sort(arr, left, right, count):

    if left + 1 < right:
        pivot = (left + right) // 2
        count = merge_sort(arr, left,  pivot, count)
        count = merge_sort(arr, pivot, right, count)

        count = merge(arr, left, pivot, right, count)
    return count

count = merge_sort(arr, 0, num, 0)
print(" ".join(list(map(str, arr))))
print(count)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L, R = [0] * (n1 + 1), [0] * (n2 + 1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = float('INF')
    R[n2] = float('INF')

    i, j = 0, 0
    compare_cnt = 0
    for k in range(left, right):
        compare_cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return compare_cnt


def merge_sort(A, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(A, left, mid)
        cnt += merge_sort(A, mid, right)
        cnt += merge(A, left, mid, right)
    return cnt


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    cnt = merge_sort(A, 0, N)
    print(*A)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global counter
    INFTY = 10 ** 10
    L = A[left:mid]
    R = A[mid:right]
    L.append(INFTY)
    R.append(INFTY)
    i, j = 0, 0
    for k in range(left, right):
        counter += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 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()))

counter = 0
merge_sort(A, 0, n)
print(' '.join(str(a) for a in A))
print(counter)

Submission status: Accepted

Solution code:
import math

def merge(a,l,m,r):
    global cnt
    L = a[l:m]+[math.inf]
    R = a[m:r]+[math.inf]
    i = 0
    j = 0
    for k in range(l,r):
        cnt+=1
        if L[i]<=R[j]:
            a[k] = L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
def mergeSort(a,l,r):
    if l+1<r:
        m = (l+r)//2
        mergeSort(a,l,m)
        mergeSort(a,m,r)
        merge(a,l,m,r)
n = int(input())
a = list(map(int, input().split()))
cnt = 0

mergeSort(a,0,n)
print(*a)
print(cnt)

Submission status: Accepted

Solution code:
import math


def merge(S, left, mid, right) -> int:
    # n1 = mid - left
    # n2 = right - mid
    L = S[left: mid]
    R = S[mid: right]

    # for i in range(n1):
    #     L.append(S[left + i])
    L.append(math.inf)

    # for i in range(n2):
    #     R.append(S[mid + i])
    R.append(math.inf)

    i = 0
    j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1

    return right - left


def merge_sort(S, left, right):
    count = 0

    if left + 1 < right:
        mid = int((left + right) / 2)
        count += merge_sort(S, left, mid)
        count += merge_sort(S, mid, right)
        count += merge(S, left, mid, right)

    return count


def main():
    n = int(input())
    S = list(map(int, input().split()))
    count = 0

    count = merge_sort(S, 0, n)

    print(*S)
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
counter = 0


def merge(A, left, mid, right):
    m = mid - left
    n = right - mid
    L = [None] * (m+1)
    R = [None] * (n+2)

    for i in range(m):
        L[i] = A[left + i]

    for i in range(n):
        R[i] = A[mid + i]

    L[m], R[n] = float("inf"), float("inf")  # stoper
    i, j = 0, 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    global counter
    counter += right - left
    return


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)
    return A


def main():
    _ = input()
    A = [int(i) for i in input().strip().split()]
    merge_sort(A, 0, len(A))
    print(" ".join([str(i) for i in A]))


if __name__ == "__main__":
    counter = 0
    main()
    print(counter)

Submission status: Accepted

Solution code:
import math
inf = math.inf

def merge(A, left, mid, right):
    global cnt
    
    L = []
    R = []
    for i in A[left:mid]:
        L.append(i)
    for i in A[mid:right]:
        R.append(i)
    L.append(inf)
    R.append(inf)
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if right - left > 1:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

_ =input()
A = list(map(int, input().rstrip().split(" ")))
cnt = 0
mergeSort(A, 0, len(A))

print(" ".join(list(map(str, A))))
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

if __name__ == '__main__':
  n = int(input())
  A = list(map(int, input().split()))
  cnt = 0

  def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L=[10**9+1]*(n1+1) # 先に入れきった方の配列をヌルポにしないため
    R=[10**9+1]*(n2+1)
    for i in range(n1):
      L[i] = A[left + i]
    for i in range(n2):
      R[i] = A[mid + i]
    i = 0
    j = 0
    for k in range(left, right):
      cnt += 1
      if L[i] <= R[j]:
        A[k] = L[i]
        i += 1
      else:
        A[k] = R[j]
        j += 1

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

  mergeSort(A, 0, n)
  print(*A)
  print(cnt)

Submission status: Accepted

Solution code:
import sys

INF = 10**9

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]

z = 0


def merge(A, left, right):

    global z

    n1 = (right - left) // 2 + left  # L側の個数

    # L[0...n1], R[0...n2] を生成
    # L = A[left:n1].copy()
    # R = A[n1:right].copy()

    L = A[left:n1]
    R = A[n1:right]


    L.append(INF)
    R.append(INF)

    # print(L, R)

    i = 0
    j = 0
    for k in range(left, right):
        z += 1 

        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


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


mergesort(A, 0, N)

print(" ".join([str(x) for x in A]))
print(z)

Submission status: Accepted

Solution code:
import math
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [math.inf]
    R = A[mid:right] + [math.inf]

    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


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


n = int(input())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)

print(' '.join(str(a) for a in A))
print(cnt)