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] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right) Input In the first line 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 ≤ 10 9  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

Solution (Python):
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]
    
    
    
    
    
    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):

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)

Solution (Python):
"""
マージソート
分割統治法に基づく高速なアルゴリズム。
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)

Solution (Python):

cnt = 0
SENTINEL = 2000000000

def merge(arr, length, left, mid, right):



    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)

Solution (Python):
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)

Solution (Python):
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}")

Solution (Python):
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)

Solution (Python):
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):
    
    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

Solution (Python):







BIG_NUM = 2000000000




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










    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)



print(*S)
print(count)

Solution (Python):
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)

Solution (Python):




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;

    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



    return(count)

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

        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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
count = 0
INF = float('inf')
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 = i+1
        else:
            A[k] = R[j]
            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)





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

Solution (Python):
def merge(L,R):
  T=[]
  for l in L[::-1]:
    while R and R[-1] > l:
      T += [R.pop()]
    T += [l]
  return R+T[::-1]

def mergesort(A):
  l = len(A)
  global c
  c += l
  s = l // 2
  return merge(mergesort(A[:s]),mergesort(A[s:])) if l > 1 else A

def solver():
  print(*mergesort(list(map(int,input().split()))))
  print(c)

c = -int(input())


solver()

Solution (Python):
INFTY = 1000000001

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

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

    L.append(INFTY)
    R.append(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

        cnt += 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 = list(map(int, input().split()))

cnt = 0

merge_sort(S, 0, len(S))


print(*S)
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    count = 0
    INF = 1000000000000000000000
    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
    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_left = merge_sort(A, left, mid)
        count_right = merge_sort(A, mid, right)
        count = merge(A, left, mid, right)
        return count + count_right + count_left
    return 0


def main():
    global A
    n = int(input())
    A = list(map(int, input().split()))
    count = merge_sort(A, 0, len(A))
    print(" ".join([str(a) for a in A]))
    print(count)

main()

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

count = 0

def merge(A, left, mid, right):
    global count
    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] = 1.0e+9 + 1
    R[n2] = 1.0e+9 + 1
    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 = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

mergeSort(A, 0, len(A))

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

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    MAX = 500000
    SENTINEL = 2000000000

    L = [None]*(MAX//2+2)
    R = [None]*(MAX//2+2)
    cnt = 0

    def merge(A, n ,left, mid, right, cnt):
        n1 = mid - left
        n2 = right - mid
        for i in range(n1):
            L[i] = A[left + i]
        for i in range(n2):
            R[i] = A[mid + i]
        L[n1] = R[n2] = 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
        return cnt

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

    n = int(input())

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

    cnt = mergeSort(A, n, 0, n, cnt)

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

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

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    i = 0
    j = 0
    L.append(1000000000)
    R.append(1000000000)
    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 A

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

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

Solution (Python):
n = int(input())
nums = [int(i) for i in input().split(" ")]

count = 0

def merge(nums, left, mid, right):
    i = 0
    j = 0
    nums_l = nums[left:mid]
    nums_r = nums[mid:right]
    nums_l.append(10 ** 9 + 1)
    nums_r.append(10 ** 9 + 1)
    for x in range(0, right - left):
        global count
        count = count + 1
        if nums_l[i] <= nums_r[j]:
            nums[left + x] = nums_l[i]
            i = i + 1
        else:
            nums[left + x] = nums_r[j]
            j = j + 1

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

merge_sort(nums, 0, n)
result = ""
for i in nums:
    result += str(i) + " "
print(result.rstrip())
print(count)

Solution (Python):
def merge(A, left, mid, right):
    inf = float("inf")
    L, R = A[left:mid]+[inf], 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 merge_sort(A, left, right, count=0):
    if left+1 < right:
        mid = (left + right) // 2
        count = merge_sort(A, left, mid, count)
        count = merge_sort(A, mid, right, count)
        count += merge(A, left, mid, right)

    return count


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

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

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

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

Solution (Python):
count = 0


def merge(A, left, mid, right):
    L = A[left:mid] + [float('INF')]
    R = A[mid:right] + [float('INF')]
    i = 0
    j = 0
    
    for k in range(left, right):
        global count
        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())
A = list(map(int, input().split()))
mergeSort(A, 0, len(A))
print(*A)
print(count)

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

def merge(A,left,mid,right,B):
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000000)
    R.append(1000000000)

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

n = int(input())
nums = list(map(int,input().split(" ")))
B = []

mergeSort(nums,0,n,B)
print(' '.join(map(str,nums)))
print(str(len(B)))

Solution (Python):
INF = 10 ** 10


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
        countL = merge_sort(A, left, mid)
        countR = merge_sort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0


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

Solution (Python):
count = 0

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


def merge_sort(a):
    if len(a) == 1:
        return [a[0]]
    mid = len(a) // 2
    l1 = merge_sort(a[:mid])
    l2 = merge_sort(a[mid:])
    merged = merge(l1, l2)
    return merged


def merge(l1, l2):
    global count
    len_l1 = len(l1)
    len_l2 = len(l2)
    l1c = l1.copy()
    l2c = l2.copy()

    l1c.append(10 ** 10)
    l2c.append(10 ** 10)

    i = 0
    j = 0
    r = []
    
    
    for k in range(len_l1 + len_l2):
        
        
        count += 1
        if l1c[i] <= l2c[j]:
            r.append(l1c[i])
            i += 1
        else:
            r.append(l2c[j])
            j += 1
    return r


r = merge_sort(l)
print(" ".join([str(i) for i in r]))
print(count)

Solution (Python):
SENTINEL = 1e+9
t = 0


def Merge(A, left, mid, right):
    global t
    n1 = mid - left
    n2 = right - mid
    L, R = A[left:left+n1], A[mid:mid+n2]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(left, right):
        t += 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)


def main():
    global t
    input()
    A = [int(i) for i in input().split()]
    Merge_Sort(A, 0, len(A))
    print(*A)
    print(t)


if __name__ == '__main__':
    main()

Solution (Python):


INF = 10000000000
count = 0

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 = 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)
         
    return 0
          
  
n = int(input())
A = [int(i) for i in input().split()]

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

Solution (Python):

import sys

def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    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 = int((left + right)/2);
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

n = int(input().rstrip())
A = list(map(int,input().rstrip().split()))
count = 0
mergeSort(A, 0, n)
print(" ".join(map(str,A)))
print(count)

Solution (Python):
cnt = 0

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

    L = A[left:mid]
    R = A[mid:right]
    L.append(10000000000)
    R.append(10000000000)

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

Solution (Python):
import sys, math
input = sys.stdin.readline

MAX = 2e9

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    L.append(MAX)
    R = A[mid:right]
    R.append(MAX)
    merged = []
    index_L = 0
    index_R = 0
    comp_cnt = 0
    for _ in range(n1+n2):
        cand_L = L[index_L]
        cand_R = R[index_R]
        comp_cnt += 1
        if (cand_L < cand_R):
            merged.append(cand_L)
            index_L += 1
        else:
            merged.append(cand_R)
            index_R += 1
    A[left:right] = merged
    return comp_cnt
        
def merge_sort(A, left, right):
    comp_cnt = 0
    if (left + 1 < right):
        
        mid = (left + right) // 2
        
        _, cnt = merge_sort(A, left, mid)
        comp_cnt += cnt
        _, cnt = merge_sort(A, mid, right)
        comp_cnt += cnt
        
        comp_cnt += merge(A, left, mid, right)
    return A, comp_cnt

def main():
    N = int(input())
    S = list(map(int, input().split()))
    left = 0
    right = len(S)
    merged, cnt = merge_sort(S, left, right)
    print(" ".join([str(x) for x in merged]))
    print(cnt)

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

INF = 1000000007

def merge(A, l, m, r):
    global count
    L = A[l:m] + [INF]
    R = A[m:r] + [INF]
    li = 0
    ri = 0
    for j in range(l, r):
        count += 1
        if L[li] <= R[ri]:
            A[j] = L[li]
            li += 1
        else:
            A[j] = R[ri]
            ri += 1

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

n = int(stdin.readline().rstrip())
S = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
mergeSort(S, 0, n)
print(*S)
print(count)

Solution (Python):
def merge(A, left, mid, right):
    L = A[left:mid] + [2147483648]
    R = A[mid:right] + [2147483648]
    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
    global c
    c += right - left


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


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