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:
n = int(input())
S = list(map(int, input().split()))
c = 0


def merge(left, mid, right):
    global c
    L = S[left:mid] + [float('inf')]
    R = S[mid:right] + [float('inf')]
    i, j = 0, 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
    c += right - left


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


merge_sort(0, n)

print(*S)
print(c)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/5/ALDS1_5_B

n = int(input())
A = list(map(int, input().split()))
	
# マージソート
def merge_sort(arr, left, right):
	# merge_sort(lst, 0, len(lst))
	global cnt
	if right - left == 1:
		return 
	mid = left + (right - left) // 2
	merge_sort(arr, left, mid)
	merge_sort(arr, mid, right)
	a = [arr[i] for i in range(left, mid)] \
		+ [arr[i] for i in range(right - 1, mid - 1, -1)]
	iterator_left = 0
	iterator_right = len(a) - 1
	for i in range(left, right):
		cnt += 1
		if a[iterator_left] <= a[iterator_right]:
			arr[i] = a[iterator_left]
			iterator_left += 1
		else:
			arr[i] = a[iterator_right]
			iterator_right -= 1

cnt = 0
merge_sort(A, 0, n)
print(*A)
print(cnt)

Submission status: Accepted

Solution code:
import math

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

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

  global  count

  L = A[left:mid]
  L.append(math.inf)
  R = A[mid:right]
  R.append(math.inf)
  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)
x = list(map(str,A))
print(" ".join(x))
print(count)

Submission status: Accepted

Solution code:
comparison = 0

def merge(A,left,mid,right):
    global comparison
    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] = 1e12
    R[n2] = 1e12

    i = 0
    j = 0

    for k in range(left,right):
        comparison += 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)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mergesort(A,0,n)
    print(*A)
    print(comparison)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
c = 0

def merge(a,l,m,r):
    global c
    n1 = m-l
    n2 = r-m
    L = a[l:m]
    R = a[m:r]
    L.append(1000000009)
    R.append(1000000009)
    i,j = 0,0
    for k in range(l,r):
        if L[i]<=R[j]:
            a[k] = L[i]
            i += 1
        else :
            a[k] = R[j]
            j += 1
        c+=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)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
MAXINT = 1000000001

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


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


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

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

Submission status: Accepted

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

def merge(A, left, mid, right):
	global count
	n1 = mid - left
	n2 = right - mid
	L = A[left:mid]
	R = A[mid:right]
	L.append(10000000000)
	R.append(10000000000)
	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(S, 0, n)
print(" ".join(map(str, S)))
print(count)

Submission status: Accepted

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


def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = A[left: left + n1]
    R = A[mid: mid + n2]
    L.append(float('inf'))
    R.append(float('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
        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)


merge_sort(S, 0, n)
print(*S)
print(count)

Submission status: Accepted

Solution code:
# Merge sort マージソート
# 与えられたリストAをマージソートして返す。
def mergesort(A, left, right):
    mid = int((left + right) / 2)
    if left + 1 >= right:
        return 0
    else:
        cnt = 0
        cnt += mergesort(A, left, mid)
        cnt += mergesort(A, mid, right)
        cnt += merge(A, left, mid, right)
        return cnt


def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    l1, l2 = len(L), len(R)
    i1, i2 = 0, 0
    L += [2000000000]
    R += [2000000000]
    cnt = 0
    for k in range(l1 + l2):
        cnt += 1
        if L[i1] <= R[i2]:
            A[left + k] = L[i1]
            i1 += 1
        else:
            A[left + k] = R[i2]
            i2 += 1
    return cnt


n = int(input())
S = [int(i) for i in input().split()]
mergecnt = mergesort(S, 0, n)
for i in range(0, n - 1):
    print(S[i], end=" ")
print(S[n - 1])
print(mergecnt)

Submission status: Accepted

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

def merge(A, left, mid, right):
  global count
  n1 = mid - left
  n2 = right - mid
  L = A[left:left+n1]
  R = A[mid:mid+n2]
  L.append(10**9+1)
  R.append(10**9+1)
  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

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(*S)
print(count)

Submission status: Accepted

Solution code:
def merge(arr, left: int, mid: int, right: int) -> int:
    n1 = mid - left
    n2 = right - mid
    L = [arr[left + i] for i in range(n1)]
    R = [arr[mid + i] for i in range(n2)]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 0
    cnt = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
    return cnt

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


N = int(input())
A = list(map(int, input().split()))
INF = float('inf')
cnt = 0


def merge(left, mid, right):
    global cnt
    L = A[left:mid]+[INF]
    R = A[mid:right]+[INF]
    l = 0
    r = 0

    for i in range(right-left):
        cnt += 1
        if L[l] < R[r]:
            A[left+i] = L[l]
            l += 1
        else:
            A[left+i] = R[r]
            r += 1


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


merge_sort(0, N)
print(*A)
print(cnt)

Submission status: Accepted

Solution code:
import sys,collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = 0
def merge(a,left,mid,right):
  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):
    global c
    c += 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 1 < right - left:
    mid = (left+right)//2
    mergeSort(a,left,mid)
    mergeSort(a,mid,right)
    merge(a,left,mid,right)

mergeSort(a,0,n)
print(" ".join(map(str,a)))
print(c)

Submission status: Accepted

Solution code:
INF = 10000000000

def merge(A, left, mid, right):
    count = 0
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    
    i, j = 0, 0
    for k in range(left, right):
        count = 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
        countL = mergeSort(A, left, mid)
        countR = mergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0
        

n = int(input())
A = [int(i) for i in input().split()]
count = mergeSort(A, 0, n)
for i in range(n):
    if i:
        print(" ", end = "")
    print(A[i], end = "")
print()
print(count)

Submission status: Accepted

Solution code:
count = 0

def Merge(arr, left, mid, right):

    global count

    inf = 10000000000
    n1 = mid - left
    n2 = right - mid
    L = arr[left:left + n1] + [inf]
    R = arr[mid:mid + n2] + [inf]

    i = j = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
            count += 1      
        else:
            arr[k] = R[j]
            j += 1
            count += 1
            
def MergeSort(arr, left, right):
    if (left + 1) < right:
        mid = int((left + right)/2)
        MergeSort(arr, left, mid)
        MergeSort(arr, mid, right)
        Merge(arr, left, mid, right)

def Main():
    n = int(input())
    arr = [int(a) for a in input().split()]

    MergeSort(arr, 0, n)

    print(*arr)
    print(count)

Main()

Submission status: Accepted

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

    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])

    L.append(10**9)
    R.append(10**9)

    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):
    if left + 1 < right:
        mid = (left + right)//2
        return mergeSort(A, left, mid) + mergeSort(A, mid, right) + merge(A, left, mid, right)
    else:
        return 0

n = int(input())
X = list(map(int, input().split()))
x = mergeSort(X, 0, n)

print(" ".join(map(str, X)))
print(x)

Submission status: Accepted

Solution code:
inf = 10**9 + 7


def merge(A, left, mid, right):
    cnt = 0
    L = A[left:mid]
    R = A[mid:right]
    L.append(inf)
    R.append(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
        cnt += 1
    return 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


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

Submission status: Accepted

Solution code:
INF = 10000000000

def merge(A, left, mid, right):
    count = 0
    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
    
n = int(input())
A = [int(i) for i in input().split()]
count = mergesort(A, 0, n)
for i in range(n):
    if i:
        print(" ", end = "")
    print(A[i], end = "")
print()
print(count)

Submission status: Accepted

Solution code:
MAX = 5 * 10**5
SENTINEL = 2 * 10**9
cnt = 0

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

    global cnt

    L.append(SENTINEL)
    R.append(SENTINEL)
    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())
s = list(map(int, input().split()))
mergeSort(s, 0, len(s))

ans = []
for item in s:
    ans.append(str(item))
print(' '.join(ans))
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
num_list = [int(item) for item in input().split()]


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

    L = A[left : mid] + [100**5]
    R = A[mid: right] + [100**5]
 
    cnt = 0
    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
        # print(A, left, mid, right)
    return cnt


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


res_cnt = mergeSort(num_list, 0, N)
print(*num_list)
print(res_cnt)

Submission status: Accepted

Solution code:
INF = 2*int(1e9)
cnt = 0
def merge(A, left, mid, right):
    global cnt
    nl = mid - left
    nr = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(INF)
    R.append(INF)
    i = 0
    j = 0
    for k in range(left, right):
        cnt = cnt +  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)

def main():
    n = int(input())
    s = [int(i) for i in input().split()]
    mergeSort(s, 0, n)
    for i in range(n):
        if i == n-1:
            print(s[i])
        else:
            print(s[i], end=' ')

    print(cnt)
main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

INF = 10**10

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    a1 = [A[i+left] for i in range(n1)]
    a2 = [A[i+mid] for i in range(n2)]
    a1.append(INF)
    a2.append(INF)
    
    a1_i = a2_i = 0
    
    for i in range(right-left):
        if a1[a1_i] <= a2[a2_i]:
            A[left+i] = a1[a1_i]
            a1_i += 1
        else:
            A[left+i] = a2[a2_i]
            a2_i += 1
    return right-left
    
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)
        
        #print('l={}, r={}, m={}'.format(left, right, mid))    
        #print(*A)
        
    return cnt

n = int(input())
S = [int(i) for i in input().split()]

cnt = merge_sort(S, 0, n)

print(*S)
print(cnt)

Submission status: Accepted

Solution code:
INFTY = 10 ** 9
count = 0

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

    n1 = mid - left
    n2 = right - mid

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

    i = 0
    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 += 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(count)

Submission status: Accepted

Solution code:
INFTY=1000000000

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

def merge(A,left,mid,right):
    cnt=0
    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(INFTY)
    R.append(INFTY)
    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
    return cnt

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

cnt=mergeSort(A,0,n)
print(' '.join(map(str,A)))
print(cnt)

Submission status: Accepted

Solution code:
INF = 10000000000


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


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__":
    global count
    count = 0
    input()
    A = [int(x) for x in input().split()]
    mergeSort(A, 0, len(A))
    print(' '.join(map(str, A)))
    print(count)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(10**9+1)
    R.append(10**9+1)
    i = 0
    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 merge_sort(A, left, right):
    if left+1 < right:
        mid = (left+right)//2
        ans1 = merge_sort(A, left, mid)
        ans2 = merge_sort(A, mid, right)
        return merge(A, left, mid, right)+ans1+ans2
    return 0


N = int(input())
S = list(map(int, input().split()))
ans = merge_sort(S, 0, N)
print(*S)
print(ans)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    """ merge list a[left:mid] and a[mid:right], assuming the lists is sorted
    """
    global cnt
    inf = 10 ** 9
    left_a = a[left:mid] + [inf]
    right_a = a[mid:right] + [inf]
    
    i, j = 0, 0

    for k in range(left, right):
        if left_a[i] <= right_a[j]:
            a[k] = left_a[i]
            i += 1
        else:
            a[k] = right_a[j]
            j += 1

        cnt += 1


def merge_sort(a, left, right):
    """ split list a[left:right-1] into two lists and merge
    """
    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()))
cnt = 0
merge_sort(a, 0, n)

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

Submission status: Accepted

Solution code:
def merge(A, l, m, r):
    n1 = m - l
    n2 = r - m
    
    L = [A[l+i] for i in range(n1)]
    R = [A[m+i] for i in range(n2)]
    L.append(10**10)
    R.append(10**10)
    
    i = 0
    j = 0
    for k in range(l, r):
        if L[i]<=R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    global cnt
    cnt += i+j
    #print(cnt)
    return i+j
    
def mergeSort(A, l, r):
    if l+1<r:
        mid = (l + r)//2;
        mergeSort(A, l, mid)
        mergeSort(A, mid, r)
        merge(A, l, mid, r)


n = int(input())
A = list(map(int, input().split()))
#n = 10
#A = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]
cnt = 0

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
SWAP = 0

def conquer(A, left, mid, right):
  L, R = A[left:mid], A[mid:right]
  # L, Rの末尾にINFTYを入れないと、L[-1] or R[-1]が評価されない
  INFTY = 2 ** 30
  L.append(INFTY)
  R.append(INFTY)
  # i : position in L, j : position in R
  i, j = 0, 0

  swap_times =  0

  # 元のArrayを変えたいため、kを生成
  for k in range(left, right):
    # print(i, j, L, R, A)
    if L[i] <= R[j]:
      A[k] = L[i]
      i = i + 1
    else:
      A[k] = R[j]
      j = j + 1
    swap_times += 1

  return swap_times

def divide(A, left, right):
  # print(left, right)

  # A[right-left]が2つ以上の場合に
  if left+1 < right:
    mid = (left+right)//2

    countL = divide(A, left, mid)
    countR = divide(A, mid, right)

    return conquer(A, left, mid, right) + countL + countR

  return 0

def mergeSort(A):
  return divide(A, 0, len(A))

swap = mergeSort(A)

print(" ".join([ str(i) for i in A]))
print(swap)

Submission status: Accepted

Solution code:
INFTY = float('inf')
count = 0

def merge(A, left, mid, right):
    L = A[left:mid] + [INFTY]
    R = A[mid:right] + [INFTY]
    i, j = 0, 0  
    global count 
    
    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 = list(map(int, input().split()))

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

Submission status: Accepted

Solution code:
INF = float("INF")

def merge(A, left, mid, right):
    count = 0
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    
    i, j = 0, 0
    for k in range(left, right):
        count = 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
        countL = mergeSort(A, left, mid)
        countR = mergeSort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0
        

n = int(input())
A = [int(i) for i in input().split()]
count = mergeSort(A, 0, n)
for i in range(n):
    if i:
        print(" ", end = "")
    print(A[i], end = "")
print()
print(count)

Submission status: Accepted

Solution code:
#初期定義
global result
global s_list
result = 0

#アルゴリズム：ソート
def merge(left, mid, right):
    global result
    
    n1 = mid - left
    n2 = right - mid
    inf = 10**9
    L_list = s_list[left: mid] + [inf]
    R_list = s_list[mid: right] + [inf]

    i = 0
    j = 0
    for k in range(left, right):
        result += 1
        if L_list[i] <= R_list[j]:
            s_list[k] = L_list[i]
            i += 1
        else:
            s_list[k] = R_list[j]
            j += 1

#アルゴリズム：マージソート
def mergeSort(left, right):
    if (left + 1) < right:
        mid = (left + right) // 2
        mergeSort(left, mid)
        mergeSort(mid, right)
        merge(left, mid, right)

#初期値
n = int(input())
s_list = list(map(int, input().split()))

#処理の実行
mergeSort(0, n)

#結果の表示
print(" ".join(map(str, s_list)))
print(result)

Submission status: Accepted

Solution code:
def merge(A,left,mid,right):
    INF = 10**9
    n1 = mid - left
    n2 = right - mid
    #L[0…n1], R[0…n2]を生成
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append(INF)
    R.append(INF)
    i = 0
    j = 0
    c = 0
    for k in range(left,right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return c

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

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

Submission status: Accepted

Solution code:
# Merge Sort
N = int(input())
lst = list(map(int, input().split()))

INF = 10**9 + 1
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    L.append(INF)  # 番兵
    R = A[mid:right]
    R.append(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 merge_sort(A, left, right):
    if (right - left > 1):
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
        
merge_sort(lst, 0, len(lst))
print(*lst)
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
INF = (10 ** 9) * 2
count = 0


def merge(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] = INF
    R[n2] = INF

    i = 0
    j = 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 mergesort(left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        count = 0
        count += mergesort(left, mid)
        count += mergesort(mid, right)
        return count + merge(left, mid, right)
    return 0


count = mergesort(0, len(A))

print(*A)
print(count)

Submission status: Accepted

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

def merge(left, mid, right):
    left_part = S[left:mid]
    right_part = S[mid:right]
    left_part.append(inf)
    right_part.append(inf)
    l, r = 0, 0
    for i in range(left, right):
        if left_part[l] < right_part[r]:
            S[i] = left_part[l]
            l += 1
        else:
            S[i] = right_part[r]
            r += 1
    num[0] += right-left

if __name__ == "__main__":
    num = [0]
    inf = float('inf')
    n = int(input())
    S = list(map(int, input().split()))
    merge_sort(0, n)
    print(' '.join(list(map(str, S))))
    print(num[0])

Submission status: Accepted

Solution code:
import re
import sys
INF=10000000000000
sys.setrecursionlimit(10**6)

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

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

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

print(re.sub("[\[\]\,]","",str(s)))
print(count)

Submission status: Accepted

Solution code:
inf = 10000000000

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

def merge(A, left, mid, right):
    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

if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    ans = merge_sort(A, 0, n, 0)
    print(*A)
    print(ans)

Submission status: Accepted

Solution code:
count=0
def mg(S,left,right,mid):
    global count
    L=[]
    L=S[left:mid]
    L.append(9999999999)
    R=[]
    R=S[mid:right]
    R.append(9999999999)
    r=0
    l=0
    for i in range(left,right):
        count=count+1
        if L[l]<=R[r]:
            S[i]=L[l]
            l=l+1
        else:
            S[i]=R[r]
            r=r+1
def ms(S,left,right):
    if right>left+1:
        mid=(right+left)//2
        ms(S,left,mid)
        ms(S,mid,right)
        mg(S,left,right,mid)
n=int(input())
S=[]
S=input().split()
S=[int(u) for u in S]
ms(S,0,n)
for i in range(0,n-1):
    print(S[i],end=" ")
print(S[n-1])
print(count)

Submission status: Accepted

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

	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
	count += right - left

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

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