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):
    global count

    n1 = mid-left
    n2 = right-mid

    L = [0]*(n1+1)
    for i in range(n1):
        L[i] = A[left+i]
    
    R = [0]*(n2+1)
    for i in range(n2):
        R[i] = A[mid+i]
    
    L[n1] = 10000000000
    R[n2] = 10000000000

    i, j = 0, 0 
    for k in range(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j+1
    return count
    
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        #sortする
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        #統合する
        merge(A, left, mid ,right)


n = int(input())
s = list(map(int, input().split()))
mergeSort(s, 0, n)
s = map(str, s)
print(' '.join(s))
print(count)

Submission status: Accepted

Solution code:
n = int(input())

S = list(map(int, input().split()))

c = 0

def merge(A, left, mid, right):
  inf = float('inf')
  L = A[left:mid] + [inf]
  R = A[mid:right] + [inf]
  i = 0
  j = 0
  global c
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
      c += 1
    else:
      A[k] = R[j]
      j += 1
      c += 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(S, 0, n)

print(" ".join(map(str, S)))

print(c)

Submission status: Accepted

Solution code:
import math
import sys

# 比較回数をここに記録
# 理論上 n * lg n を越えることはない。
_exchange = 0

def merge_sort(A, left, right):
    """数列 A を in place に昇順にソートする。

    left は A の先頭のインデックス、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):
    """ソート済みの部分列をマージする。

    数列 A の left から mid - 1 の要素、mid から right - 1 までの
    ２つの部分列はソート済みである。これをマージして、left から right - 1 まで
    ソートする。
    """
    first = A[left:mid]
    first.append(math.inf)  # 番兵
    second = A[mid:right]
    second.append(math.inf) # 番兵

    global _exchange
    i = j = 0
    for k in range(left, right):
        _exchange += 1
        if first[i] <= second[j]:
            A[k] = first[i]
            i += 1
        else:
            A[k] = second[j]
            j += 1


if __name__ == '__main__':
    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))

    merge_sort(A, 0, n)
    print(*A)
    print(_exchange)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):

    inf = float('inf')
    L = A[left:mid]+[inf]
    R = A[mid:right] + [inf]

    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 right - left


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

n  = int(input())
A = list(map(int, input().split()))
ans = mergeSort(A, 0, n)
s = list(map(str, A))
print(' '.join(s))
print(ans)

Submission status: Accepted

Solution code:
count = 0

def merge_sort(n, nums):
    if n == 1:
        return nums
    left_n = n // 2  # 左側が小さい
    left_sorted = merge_sort(left_n, nums[:left_n]) + [10**9 + 1]  # 番兵
    right_n = n - left_n
    right_sorted = merge_sort(right_n, nums[left_n:]) + [10**9 + 1]  # 番兵
    left_idx = 0
    right_idx = 0
    idx = 0
    sorted_list = [0] * n
    while idx < n:
        if left_sorted[left_idx] < right_sorted[right_idx]:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]
            right_idx += 1
        idx += 1
    global count
    count += idx
    return sorted_list


def main():
    n = int(input())
    nums = list(map(int, input().split(" ")))
    sorted_list = merge_sort(n, nums)
    print(" ".join(map(str, sorted_list)))
    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = int(1e18)

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    L.append(INF)
    R.append(INF)
    i, j = 0, 0
    count = 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 merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        c1 = merge_sort(A, left, mid)
        c2 = merge_sort(A, mid, right)
        c = merge(A, left, mid, right)
        return c + c1 + c2
    else:
        return 0

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

    print(" ".join(map(str, A)))
    print(c)

Submission status: Accepted

Solution code:
INF = 10000000000

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

    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]

    i, j= 0, 0

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

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

if __name__ == '__main__':
    n = int(input())
    S = [int(x) for x in input().split()]
    anw = 0
    mergeSort(S, 0, n)
    print(*S)
    print(anw)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    NL = len(L)
    NR = len(R)
    i = 0
    j = 0
    for k in range(left, right):
        if i == NL:
            A[k] = R[j]
            j += 1
        elif j == NR:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return right - left


def mergesort(A, left, right):
    ans = 0
    if right - left > 1:
        mid = (left + right) // 2
        ans += mergesort(A, left, mid)
        ans += mergesort(A, mid, right)
        ans += merge(A, left, mid, right)
    return ans


def main():
    N, *S = map(int, open(0).read().split())
    ret = mergesort(S, 0, len(S))
    print(' '.join(map(str, S)))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
cnt=0
a=list(map(int,input().split()))

def Merge(A, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L=[0]*(n1+1)
	R=[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] = 10**10
	R[n2] = 10**10
	i = 0
	j = 0
	global cnt
	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:
n = int(input())
A = list(map(int, input().split()))

count = 0

inf = 999999999999999999

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

def merge(left, right):
  global count
  result = []
  
  left.append(inf)
  right.append(inf)
  left_i = 0
  right_i = 0
  while True:
    if right[right_i] == inf:
      result.extend(left[left_i:-1])
      count += len(left[left_i:-1])
      break
    if left[left_i] == inf:
      result.extend(right[right_i:-1])
      count += len(right[right_i:-1])
      break

    if left[left_i] < right[right_i]:
      result.append(left[left_i])
      left_i += 1
    else:
      result.append(right[right_i])
      right_i += 1
    count += 1
  return result

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

Submission status: Accepted

Solution code:
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Submission status: Accepted

Solution code:
import sys

def merge(A, left, mid, right):
    L = A[left: mid] + [sys.maxsize]
    R = A[mid: right] + [sys.maxsize]
    i = j = count = 0
    k = left
    while k < right:
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1
    return count

def merge_sort(A, left, right):
    if right - left > 1:
        mid = (left + right) // 2
        lcost = merge_sort(A, left, mid)
        rcost = merge_sort(A, mid, right)
        tot = merge(A, left, mid, right)
        return tot + lcost + rcost
    else:
        return 0

if __name__ == '__main__':
    n = int(input())
    A = [int(i) for i in input().split()]
    count = merge_sort(A, 0, n)
    print(str(A).replace(',', '').replace('[', '').replace(']', ''))
    print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_right as br
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def MergeSort(aa, left=0, right=-1):
    def merge(aa, left2, mid2, right2):
        res=0
        inf = float("inf")
        L = aa[left2:mid2] + [inf]
        R = aa[mid2:right2] + [inf]
        Li = Ri = 0
        for ai in range(left2, right2):
            res+=1
            if L[Li] < R[Ri]:
                aa[ai] = L[Li]
                Li += 1
            else:
                aa[ai] = R[Ri]
                Ri += 1
        return res

    res=0
    if right == -1: right = len(aa)
    if left + 1 < right:
        mid = (left + right) // 2
        res+=MergeSort(aa, left, mid)
        res+=MergeSort(aa, mid, right)
        res+=merge(aa, left, mid, right)
    return res

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    cnt=MergeSort(aa)
    print(*aa)
    print(cnt)
main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())

c=0
left=0
right=n
def merge(A,left,mid,right):
    global c
    L=A[left:mid]+[float("inf")]
    R=A[mid:right]+[float("inf")]
    i=0
    j=0
    for r in range(left,right):
        if L[j]>R[i]:
            c+=1
            A[r]=R[i]
            i+=1
        else:
            c+=1
            A[r]=L[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,left,right)

print(*a)
print(c)

Submission status: Accepted

Solution code:
A = []
ans = 0

def merge(left, mid, right):
	global A
	global ans
	n1 = mid - left
	n2 = right - mid
	l = []
	r = []
	for i in range(n1):
		l += [A[left + i]]
	for i in range(n2):
		r += [A[mid + i]]
	l += [10**18]
	r += [10**18]
	i = 0
	j = 0
	ans += right - left
	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 Msort(left, right):
	if left + 1 < right:
		mid = int((left + right)/2)
		Msort(left, mid)
		Msort(mid,right)
		merge(left,mid,right)

def main():
	global ans
	global A
	n = int(input())
	A = list(map(int,input().split()))
	Msort(0,n)
	print(" ".join(list(map(str,A))))
	print(ans)

main()

Submission status: Accepted

Solution code:

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

    L.append(2000000000)  # これをしないとマージするとき、最後の１回でリスト外アクセスでエラー。
    R.append(2000000000)

    global count
    i, j = 0, 0

    # print('left, mid, right')
    # print(left, mid, right)

    for k in range(left, right, 1):
        count += 1
        # print('i, j, k')
        # print(i, j, k)

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

        # print('loop end')


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


N = int(input())
A = list(map(int, input().split()))
count = 0

merge_sort(A, N, 0, N)

print(' '.join(map(str, A)))
print(count)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    count =0
    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
    return count

def MergeSort(A, left, right):
    if left +1 < right:
        mid = (left + right)//2
        countR = MergeSort(A, left, mid)
        countL = MergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0

N = int(input())
A = list(map(int, input().split()))
count = MergeSort(A, 0, N)
print(" ".join(list(map(str, A))))
print(count)

Submission status: Accepted

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

    i,j=0,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(*A)
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
S=[int(i) for i in input().split()]
INF=10**10

def merge(A,l,m,r):
    cnt=0
    n1=m-l
    n2=r-m
    L,R=[0 for i in range(n1)],[0 for i in range(n2)]
    cnt=0
    L=A[l:l+n1]
    R=A[m:m+n2]
    L.append(INF)
    R.append(INF)
    i,j=0,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
    return cnt     

def mergesort(A,l,r):
    cnt=0
    if l+1<r:
        m=(l+r)//2
        cnt+=mergesort(A,l,m)
        cnt+=mergesort(A,m,r)
        cnt+=merge(A,l,m,r)
    return cnt


cnt=mergesort(S,0,n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    count = 0
    INF = 1_000_000_001
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [INF]
    R = A[mid:right] + [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


if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    count = mergeSort(nums, 0, n)
    print(*nums)
    print(count)

Submission status: Accepted

Solution code:
#ALDS1_5_B
sum = 0

def merge(A, left, mid, right):
    global sum
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1+1)
#     L = A[left:mid]
    R = [0] * (n2+1)
#     R = A[mid:right]
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 10**9
#     L.append(10**9)
    R[n2] = 10**9
#     R.append(10**9)
    i = 0
    j = 0
    for k in range(left, right):
        sum += 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())
S = list(map(int, input().split()))

mergeSort(S, 0, len(S))
print(*S)
print(sum)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
num = int(input())
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [ 1e10 ]
    R = A[mid:right] + [ 1e10 ]
    i = 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)

L = [int(x) for x in input().split()]
c = mergeSort(L, 0, len(L))
print(" ".join(map(str,L)))
print(cnt)

Submission status: Accepted

Solution code:
def merge(A,left,mid,right):
    global count

    L=A[left:mid]+[1000000001]
    R=A[mid:right]+[1000000001]

    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

    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)

n=int(input())
A=list(map(int,input().split()))
count=0
merge_sort(A,0,n)
print(*A)
print(count)

Submission status: Accepted

Solution code:
cnt=0
def merge_sort(S):
    l=len(S)
    mid=int(l/2)
    Left=S[0:mid]
    Right=S[(mid):l]
    global cnt
    
    if l>=2:
        merge_sort(Left) and merge_sort(Right)
    

    Left.append(float('inf'))
    Right.append(float('inf'))

    p=0
    q=0
    for i in range(l):
        if Left[p]<Right[q]:
            S[i]=Left[p]
            p+=1
        else:
            S[i]=Right[q]
            q+=1
    if l!=1 :
        cnt+=l
    
    return S


n=int(input())
S=list(map(int,input().split()))
merge_sort(S)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:

def merge(s, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = s[left:mid] + [1000000001]
    R = s[mid:right] + [1000000001]

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

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

n = int(input())
count = 0
s = list(map(int, input().split()))
mergesort(s, 0, n)

for i in range(len(s)-1):
      print(s[i], end = " ")
print(s[n-1])
print(count)

Submission status: Accepted

Solution code:
cnt = 0
def merge_sort(array):
    global cnt
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    cnt += len(left) + len(right)
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    list = []
    l_index, r_index = 0, 0
    while l_index < len(left) and r_index < len(right):
        if left[l_index] <= right[r_index]:
            list.append(left[l_index])
            l_index += 1
        else:
            list.append(right[r_index])
            r_index += 1
    if l_index < len(left):
        list.extend(left[l_index:])
    if r_index < len(right):
        list.extend(right[r_index:])
    
    return list

n = int(input())
S = list(map(int, input().split()))
array = merge_sort(S)
print(" ".join(map(str, array)))
print(cnt)

Submission status: Accepted

Solution code:
count=0
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[10**9+1]
    R=A[mid:right]+[10**9+1] 
    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
       
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())
S=[int(i) for i in input().split()]
mergeSort(S,0,n)
print(*S)
print(count)

Submission status: Accepted

Solution code:
cp = 0
def m(L,R):
    global cp
    j = 0
    for l in L:
        while j < len(R) and R[j] < l:
            yield R[j]
            j += 1
        yield l
    while j < len(R):
        yield R[j]
        j += 1
    cp += len(L) + len(R)
def merge(A):
    global cp
    if len(A) == 1:
        return A
    if len(A) == 2:
        cp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A
n=int(input())
A=[int(i) for i in input().rstrip().split(" ")]
B = merge(A)
print(*B)
print(cp)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    L = a[left:mid] + [INF]
    R = a[mid:right] + [INF]
    
    i = 0
    j = 0
    for k in range(left, right):
     
        global idx
        idx += 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)


INF = 1000000000
idx = 0
n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a,0,len(a))
print(*a)
print(idx)

Submission status: Accepted

Solution code:
def m(S, left, mid, right):
  global count
  L = S[left:mid]
  R = S[mid:right]
  L.append(1000000000)
  R.append(1000000000)
  i = 0
  j = 0
  for k in range(left,right):
    count = count + 1
    if L[i] <= R[j]:
      S[k] = L[i]
      i = i + 1
    else:
      S[k] = R[j]
      j = j + 1

def ms(S,left,right):
  if (left+1) < right:
    mid = (left+right)//2
    ms(S, left, mid)
    ms(S, mid, right)
    m(S, left, mid, right)

n = int(input())
S = [int(x) for x in input().split()]
left = 0
right = n
count = 0

ms(S,left,right)

for i in range(n):
  if i != (n-1):
    print(S[i], end = " ")
  else:
    print(S[i])
print(count)

Submission status: Accepted

Solution code:
#17D8103001E Fukushima Emi persimmon8 python 19.10.24

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

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

    L=A[left:mid]+[10000000000000]
    R=A[mid:right]+[100000000000000]

    i=0
    j=0
    for k in range(left,right):
        count+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else: 
            A[k]=R[j] 
            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)
d=map(str,A)
print(' '.join(d))
print(count)

Submission status: Accepted

Solution code:
import math
N=10**9 + 1
n=int(input())
a=list(map(int,input().split()))

def merge(a,left,mid,right):
    global cnt
    n=mid-left
    m=right-mid
    l=a[left:left + n]
    o=a[mid:mid + m]
    l.append(N)
    o.append(N)
    i=0
    j=0
    for k in range(left,right):
        cnt+=1
        if l[i]<=o[j]:
            a[k]=l[i]
            i+=1
        else:
            a[k]=o[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)





cnt=0
mergesort(a,0,len(a))
print(*a)
print(cnt)

Submission status: Accepted

Solution code:
def main():
    cnt = 0

    def merge(A, l, mid, r):
        nonlocal cnt
        n1 = mid - l
        n2 = r - mid
        L = [A[l + i] for i in range(n1)]
        R = [A[mid + i] for i in range(n2)]
        L.append(1 << 60)
        R.append(1 << 60)
        i = 0
        j = 0
        for k in range(l, r):
            if L[i] <= R[j]:
                cnt += 1
                A[k] = L[i]
                i = i + 1
            else:
                cnt += 1
                A[k] = R[j]
                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())
    S = [int(i) for i in input().split()]
    merge_sort(S, 0, N)
    print(*S)
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def merge(a, l, m, r):
  global count
  Left = a[l:m]
  Left.append(1e10)
  Right = a[m:r]
  Right.append(1e10)
  i, j = 0, 0
  for k in range(l, r):
    count += 1
    if Left[i] <= Right[j]:
      a[k] = Left[i]
      i += 1
    else:
      a[k] = Right[j]
      j += 1

def sort(a, l, r):
  if r-l > 1:
    m = (l+r)//2
    sort(a, l, m)
    sort(a, m, r)
    merge(a, l, m, r)
       
       
count=0
n=int(input())
a=[int(i) for i in input().split()]
sort(a, 0, n)
print(*a)
print(count)

Submission status: Accepted

Solution code:
infinity=2**35
def merge(A,left,mid,right):
  global cnt

  L=A[left:mid]
  R=A[mid:right]
  L.append(infinity)
  R.append(infinity)
  
  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(*A)
print(cnt)

Submission status: Accepted

Solution code:
global count


def merge(arr, l, mid, r):
    arr_l = list(arr[l:mid + 1])
    arr_r = list(arr[mid + 1:r + 1])
    l_index = 0
    r_index = 0
    arr_l.append(2 << 64)
    arr_r.append(2 << 64)
    global count
    for i in range(l, r + 1):
        if arr_l[l_index] <= arr_r[r_index]:
            arr[i] = arr_l[l_index]
            l_index += 1
        else:
            arr[i] = arr_r[r_index]
            r_index += 1
        count += 1


def merge_sort(arr, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)
    merge(arr, l, mid, r)


if __name__ == '__main__':
    count = 0

    n = int(input())
    arr = list(map(int, input().split()))
    merge_sort(arr, 0, len(arr) - 1)
    for i in range(n):
        if i != n - 1:
            print(arr[i], end=' ')
        else:
            print(arr[i])
    print(count)

Submission status: Accepted

Solution code:
cnt=0
def mer(l,r):
    global cnt
    ll=len(l)
    rr=len(r)
    md=[]
    i,j=0,0
    l.append(float('inf'))
    r.append(float('inf'))
    for k in range(ll+rr):
        cnt+=1
        if l[i]<=r[j]:
            md.append(l[i])
            i+=1
        else:
            md.append(r[j])
            j+=1
    return md
def mergesort(a):
    m=len(a)
    if m<=1:
        return a
    m=m//2
    l=mergesort(a[:m])
    r=mergesort(a[m:])
    return mer(l,r)
n=int(input())
a=list(map(int, input().split()))
b=mergesort(a)
for i in range(n-1):
    print(b[i],end=" ")
print(b[n-1])
print(cnt)

Submission status: Accepted

Solution code:

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

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

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

n=int(input())
S=list(map(int,input().split()))
mergeSort(S,0,n)
print(' '.join(map(str,S)))

print(cnt)

Submission status: Accepted

Solution code:
num = 0
def marge_sort(array):
    global num
    if len(array) < 2: return array
    
    mid = len(array) // 2
    left = marge_sort(array[:mid])
    right = marge_sort(array[mid:])
    
    len_l, len_r = len(left), len(right)
    left += [float("inf")]
    right += [float("inf")]
    
    marray = [0] * (len_l + len_r)
    
    l, r = 0, 0
    for i in range(len_l + len_r):
        num += 1
        if left[l] <= right[r]:
            marray[i] = left[l]
            l += 1
        else:
            marray[i] = right[r]
            r += 1
        
    return marray

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

print(" ".join(map(str, marge_sort(a))))
print(num)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    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
        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)

INF = 10000000000
n = int(input())
S = list(map(int,input().split()))
cnt = 0
mergeSort(S,0,n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
count = 0
def Merge(A, left, mid, right):
    global count
    L = A[left:mid]+[10**9]
    R = A[mid:right]+[10**9]

    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

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(' '.join([str(_) for _ in A]))
print(count)