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:
SENTINEL = 9999999999999

count = 0

def merge(S, n, left, mid, right):
    global SENTINEL
    global count
    n1 = mid - left
    n2 = right - mid
    L = S[left:mid] + [SENTINEL]
    R = S[mid:right] + [SENTINEL]
    i = 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, n, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergeSort(S, n, left, mid)
        mergeSort(S, n, mid, right)
        merge(S, n, left, mid, right)

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

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

Submission status: Accepted

Solution code:
c = 0

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

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

Submission status: Accepted

Solution code:
def merge(A,left,mid,right):
    L=A[left:mid]+[float("INF")]
    R=A[mid:right+1]+[float("INF")]
    i=0
    j=0
    global cnt
    for k in range(left,right+1):
        if L[i]<=R[j]:
            A[k]=L[i]
            i+=1
            cnt+=1
        else:
            A[k]=R[j]
            j+=1
            cnt+=1
def mergeSort(A,left,right):
    if left<right:
        mid=(left+right)//2+1
        mergeSort(A,left,mid-1)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)
n=int(input())
S=list(map(int,input().split()))
cnt=0
mergeSort(S,0,n-1)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A,l,m,r):
    L=A[l:m];R=A[m:r]
    L.append(INF);R.append(INF)
    global cnt

    i=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:
        pass
    else:
        m=(l+r)//2
        mergeSort(A,l,m)
        mergeSort(A,m,r)
        merge(A,l,m,r)

INF=10**9+1
n=int(input())
S=list(map(int,input().split()))
cnt=0

mergeSort(S,0,n)

for i in range(n):
    if i<n-1:
        print(S[i],end=' ')
    else:
        print(S[i])
print(cnt)

Submission status: Accepted

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

n = int(input())
S = list(map(int, input().split()))
SENTINEL = 1000000005
merge_count = 0


def main():
    mergeSort(S, 0, len(S))
    print(' '.join(map(str, S)))
    print(merge_count)


def merge(A, left, mid, right):
    # print("---merge start---")
    # print("A is {}".format(A))
    # print("left:{0}, mid:{1}, right{2}".format(left, mid, right))
    global merge_count

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

    # print("L:{}".format(L))
    # print("R:{}".format(R))

    i, j = 0, 0
    for k in range(left, right, 1):
        merge_count += 1
        # print("k:{0}".format(k))
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

    # print("A is {}".format(A))
    # print("----merge end----".format(A))


def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        # print("------mergeSort start--------")
        # print("left:{0}, mid:{1}, right:{2}".format(left, mid, right))
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
infty = 1000000000
count = 0

def merge(A, left, mid, right):
	global count
	L = A[left:mid]
	R = A[mid:right]
	L.append(infty)
	R.append(infty)
	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)


if __name__ == "__main__":
	n = int(input())
	S = list(map(int, input().split()))
	mergeSort(S, 0, n)
	print(' '.join(map(str, S)))
	print(count)

Submission status: Accepted

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

inf = float("inf")
cnt = 0
def MS(NL, l, r):
    if l+1 <r:
        m = (l+r)//2
        MS(NL, l, m)
        MS(NL, m, r)
        M(NL, l, m, r)

def M(NL, l, m, r):
    global cnt
    L = NL[l:m]+[inf]
    R = NL[m:r]+[inf]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] >= R[j]:
            NL[k] = R[j]
            j += 1
        else:
            NL[k] = L[i]
            i += 1
    cnt += (r-l)
    
n = int(input())
NL = list(map(int, input().split()))
MS(NL, 0, n)

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

Submission status: Accepted

Solution code:
# ALDS1_5_B Merge Sort
import sys
count = 0

def merge(A, left, mid, right):
    global count
    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, 1):
        count += 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())
S = [int(i) for i in sys.stdin.readline().strip().split()]

merge_sort(S, 0, n)
print(' '.join(map(str, S)))
print(count)

Submission status: Accepted

Solution code:
cnt = 0
def merge(a, left, mid, right):
    global cnt
    l = 0
    l_e = mid - left
    r = 0
    r_e = right - mid - 1

    L = a[left:mid + 1]
    R = a[mid + 1:right + 1]
    csr = left
    while l <= l_e and r <= r_e:
        cnt += 1
        if L[l] < R[r]:
            a[csr] = L[l]
            l += 1
        else:
            a[csr] = R[r]
            r += 1
        csr += 1
    if l == l_e + 1:
        while r <= r_e:
            a[csr] = R[r]
            r += 1
            csr += 1
            cnt += 1
    else:
        while l <= l_e:
            a[csr] = L[l]
            l += 1
            csr += 1
            cnt += 1

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


n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a, 0, n - 1)
print(' '.join(map(str, a)))
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def marge(A, left, right, mid):
    cnt = 0
    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 ** 9 + 1
    R[n2] = 10 ** 9 + 1
    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 margesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = margesort(A, left, mid)
        cnt2 = margesort(A, mid, right)
        return cnt1 + cnt2 + marge(A, left, right, mid)
    return 0

def main():
    n = int(input())
    A = list(map(int, input().split()))
    cnt = margesort(A, 0, n)
    print(' '.join(list(map(str, A))))
    print(cnt)

if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
#import time
count=0
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[2**30]
    R=A[mid:right]+[2**30]

    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 = int((left+right)/2)
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)


#start = time.time()

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

print(s[0],end='',sep='')
for i in range(1,n):
    print(" ",s[i],end='',sep='')
print()

print(count)

#end=time.time()-start
#end*=1000
#print ("Time:{0}".format(end) + "[m_sec]")

Submission status: Accepted

Solution code:
inf=float("inf")
def merge(a,left,mid,right):
    count=0
    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
    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
        return mergeSort(a,left,mid)+mergeSort(a,mid,right)+merge(a,left,mid,right)
    return 0
n=int(input())
*a,=map(int,input().split())
ans=mergeSort(a,0,n)
print(*a)
print(ans)

Submission status: Accepted

Solution code:
import sys

infty = 10**10

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

	n1 = mid -left
	n2 = right - mid

	L = [0] * n1
	R = [0] * n2

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

	L.append(infty)
	R.append(infty)

	i = 0
	j = 0
	cnt = 0

#	print(f"{left} {mid} {right} {n1} {n2}")
#	print(f"{L} {R}")
	for k in range(left,right):

		cnt += 1

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

	return cnt

#	print(A)

def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

		mid = (left + right) // 2
		cnt += mergeSort(A,left,mid)
		cnt += mergeSort(A,mid,right)
		cnt += merge(A,left,mid,right)

	return cnt

def test():

	n = int(sys.stdin.readline())
	S = list(map(int,sys.stdin.readline().split()))

	result = mergeSort(S,0,n)
	
	for i in range(n-1):
		print(f"{S[i]} ",end='')
	print(S[n-1])
	print(result)


if __name__ == "__main__":
	test()

Submission status: Accepted

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

cnt = 0

def merge(left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = S[left:left+n1]
    R = S[mid:mid+n2]
    L.append(10e10)
    R.append(10e10)
    for j in range(n2):
        R[j] = S[mid+j]
    x = 0
    y = 0
    for k in range(left, right):
        cnt += 1
        if L[x] < R[y]:
            S[k] = L[x]
            x += 1
        else:
            S[k] = R[y]
            y += 1

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

mergesort(0, n)

print(*S)
print(cnt)

Submission status: Accepted

Solution code:
INF = 10000000000

def merge(A, left, mid, right):
  L = A[left:mid] + [INF]
  R = A[mid:right] + [INF]
  i, j = 0, 0
  global count
  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)

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:
class MergeSort:
    def __init__(self, array):
        self._arr = array
        self._cnt = 0

    def _merge(self, left, mid, right):
        arr1 = self._arr[left:mid] + [float('inf')]
        arr2 = self._arr[mid:right] + [float('inf')]

        i, j = 0, 0
        for k in range(left, right):
            if arr1[i] <= arr2[j]:
                self._arr[k] = arr1[i]
                i += 1
            else:
                self._arr[k] = arr2[j]
                j += 1

        self._cnt += right - left
        return

    def _merge_sort(self, left, right):
        if right <= left + 1:
            return

        mid = (left + right) // 2
        self._merge_sort(left, mid)
        self._merge_sort(mid, right)
        self._merge(left, mid, right)
        return

    def sort(self):
        self._merge_sort(0, len(self._arr))
        return

    def print(self):
        print(*self._arr)
        print(self._cnt)

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

alg = MergeSort(arr)
alg.sort()
alg.print()

Submission status: Accepted

Solution code:
#マージソート
from collections import deque
n = int(input())
S = list(map(int, input().split()))
INFTY = 1e9 + 1

def merge(S, left, mid, right):
    global cnt
    L = deque(S[left:mid])
    R = deque(S[mid:right])
    L.append(INFTY)
    R.append(INFTY)
    for k in range(left, right):
        S[k] = (L if L[0] < R[0] else R).popleft()
    cnt += right - left
    
def merge_sort(S, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(S, left, mid)
        merge_sort(S, mid, right)
        merge(S, left, mid, right)
        
cnt = 0
merge_sort(S, 0, n)
print(*S)
print(cnt)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

MAX = 500000
GUARD = 2000000000
cnt = 0

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

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    
    L[n1] = GUARD
    R[n2] = GUARD
    i = 0
    j = 0

    global cnt
    for k in range(left, right):
        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 = list(map(int, input().split()))

    mergeSort(S, 0, n)

    print(*S)
    print(cnt)
             
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF = 10000000000

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

def merge(A,left,mid,right):
    count = 0
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    #L,Rの中身はAの中身の部分コピーだからいちいちappendするより
    #スライスしてまとめてコピーしたほうが処理が軽い
    #[INF]は番兵みたいなもの
    #[INF]を追加しておくとL,Rを調べつくしての
    #list index out of rangeを回避できる
    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
    count += right - left
    return count

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

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:
import sys

SENTINEL = 10 ** 9 + 1
cnt = 0


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

    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 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, sys.stdin.readline().split()))
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 merge_sort(A,left,right):
  if left+1 < right:
    mid = (left+right)//2
    count_l = merge_sort(A,left,mid)
    count_r = merge_sort(A,mid,right)
    return merge(A,left,mid,right) + count_l + count_r
  return 0


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

Submission status: Accepted

Solution code:
def merge(S, left, mid, right):
    INF = 10**9
    global cnt
    L = S[left: mid] + [INF]
    R = S[mid: right] + [INF]
    i = 0
    j = 0
    
    for k in range(left, right):
        cnt += 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())
S = list(map(int, input().split()))

cnt = 0
mergeSort(S, 0, n)

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

Submission status: Accepted

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


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


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


def merge(A, n, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i = 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:
def merge(A, left, mid, right, c):
    global counter
    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] = 1000000000
    R[n2] = 1000000000
    i = 0
    j = 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
    L.pop()
    R.pop()
    return c

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

if __name__ == '__main__':
    num = int(input())
    m = list(map(int,input().split()))
    c = 0
    c = mergeSort(m, 0, num, c)
    print(' '.join(map(str,m)))
    print(str(c))

Submission status: Accepted

Solution code:
# coding: utf-8
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 cnt
    global inf

    l = a[left:mid]
    r = a[mid:right]

    l.append(inf)
    r.append(inf)

    i, j = 0, 0

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


cnt = 0
inf = 1 << 32

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

merge_sort(a, 0, len(a))
print(" ".join(map(str, a)))
print(cnt)

Submission status: Accepted

Solution code:
"""
マージソート
分割統治法に基づく高速なアルゴリズム。
merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  L[0...n1], R[0...n2] を生成
  for i = 0 to n1-1
    L[i] = A[left + i]
  for i = 0 to n2-1
    R[i] = A[mid + i]
  L[n1] = INFTY
  R[n2] = INFTY
  i = 0
  j = 0
  for k = left to right-1
    if L[i] <= R[j]
      A[k] = L[i]
      i = i + 1
    else 
      A[k] = R[j]
      j = j + 1

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 cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1] + [10**9+7]
    R = A[mid:mid+n2] + [10**9+7]
    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())
As = list(map(int, input().split()))
cnt = 0
mergeSort(As,0,n)
print(*As)
print(cnt)

Submission status: Accepted

Solution code:

cnt = 0
SENTINEL = 2000000000

def merge(arr, length, left, mid, right):
#  n1 = mid - left
#  n2 = right - mid

    L = arr[left : mid]
    R = arr[mid : right]

    L.append(SENTINEL)
    R.append(SENTINEL)

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

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

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

    merge_sort(S, n, 0, n)
    print(' '.join(map(str, S)))
    print(cnt)

Submission status: Accepted

Solution code:
inf=10**10
def merge(a,left,cen,right):
    cnt=0
    n1=cen-left
    n2=right-cen
    L=[a[left+i] for i in range(n1)]+[inf]
    R=[a[cen+i] for i in range(n2)]+[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
    return cnt

def sorting(a,left,right):
    if left+1<right:
        m=(left+right)//2
        cntlr=sorting(a,left,m)+sorting(a,m,right)
        return merge(a,left,m,right)+cntlr
    return 0

n=int(input())
a=list(map(int,input().split()))
ans=sorting(a,0,n)
print(*a)
print(ans)

Submission status: Accepted

Solution code:
import sys
from typing import List


COMP_NUM = 0


def merge(elements: List[int], left: int, mid: int, right: int) -> None:
    global COMP_NUM
    n1 = mid - left
    n2 = right - mid
    left_array = [0] * (n1 + 1)
    right_array = [0] * (n2 + 1)
    left_array[0:n1] = elements[left:left + n1]
    left_array[n1] = sys.maxsize
    right_array[0:n2] = elements[mid:mid + n2]
    right_array[n2] = sys.maxsize

    i = 0
    j = 0
    for k in range(left, right):
        COMP_NUM += 1
        if left_array[i] <= right_array[j]:
            elements[k] = left_array[i]
            i += 1
        else:
            elements[k] = right_array[j]
            j += 1


def merge_sort(elements: List[int], left: int, right: int) -> None:
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(elements, left, mid)
        merge_sort(elements, mid, right)
        merge(elements, left, mid, right)


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))
    merge_sort(elements, 0, len(elements))
    print(" ".join([str(elem) for elem in elements]))
    print(f"{COMP_NUM}")

Submission status: Accepted

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

c=0
n = int(input())
A = [int(i) for i in input().split()]
c=merge_sort(A,0,n)
print(*A)
print(c)

Submission status: Accepted

Solution code:
INF = 10**9 + 1
cnt = 0


def merge(A, left, mid, right):
    global INF, cnt
    L = []
    R = []
    for i in range(left, mid):
        L.append(A[i])
    L.append(INF)
    for i in range(mid, right):
        R.append(A[i])
    R.append(INF)

    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
        cnt += 1


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


if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    merge_sort(A, 0, n)
    for x in A:
        print x,
    print
    print cnt

Submission status: Accepted

Solution code:
#from enum import Enum
#from queue import Queue
#import collections

#import sys
#import math

BIG_NUM = 2000000000
#MOD = 1000000007
#EPS = 0.000000001


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

mergeSort(S,0,n)
#for i in range(n-1):
#    print("%d"%(S[i]),end=" ")
#print("%d"%(S[n-1]))
print(*S)
print(count)

Submission status: Accepted

Solution code:
cnt = 0


def merge(a, left, mid, right):
    global cnt
    i = left
    j = mid+1
    b = []
    while i <= mid and j <= right:
        if a[i] <= a[j]:
            cnt+=1
            b.append(a[i])
            i += 1
        else:
            cnt+=1
            b.append(a[j])
            j += 1
    if i == mid+1:
        while j <= right:
            cnt+=1
            b.append(a[j])
            j += 1
    else:
        while i <= mid:
            cnt+=1
            b.append(a[i])
            i += 1
    a[left:right+1] = b


def merge_sort(a, left, right):
    if left == right:
        return

    mid = (left+right)//2
    merge_sort(a, left, mid)
    merge_sort(a, mid+1, right)
    merge(a, left, mid, right)

n = int(input())
l = list(map(int,input().split()))
merge_sort(l,0,n-1)
for i in range(n-1):
    print(l[i],end = ' ')
print(l[-1])
print(cnt)

Submission status: Accepted

Solution code:
#前の問題で、戻り値とかIDとか変更したつもりのリストが変わっていないことが
#頻発していたはずだがとりあえず並び替え自体は終わる。countどうしようか。
#いじると並び替え前の配列が返ってくることがある。

n=int(input())
A1=input().split( )
A=[int(A1[i]) for i in range(n)]
###疑似コードのコピペ
def merge(A, left, mid, right):
    n1 = mid - left;
    n2 = right - mid;
#いちいち[0 for i...]を作るのやめた
    L=A[left:mid]+[10000000000]
    R=A[mid:right]+[10000000000]
    
    i = 0
    j = 0
    count=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

#count+=1の位置を変更,比較ってinfinityとの比較も含めるのか
#計算量的には当然か。
    return(count)

def mergeSort(A, left, right):
    count=0
    mid=0
    if left+1 < right:
        mid = int((left + right)/2)
#この辺で新しい変数をmergeSortの戻り値として定義
        countL=mergeSort(A, left, mid)
        countR=mergeSort(A, mid, right)
        countM=merge(A, left, mid, right)
        count=countL+countR+countM
    return(count)
c=mergeSort(A,0,n)
print(*A)
print(c)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    i = 0
    j = 0

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


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


if __name__ == '__main__':
    main()