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

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)

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

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

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

Solution (Python):



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

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

cnt = merge_sort(S, 0, n)

print(*S)
print(cnt)

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

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

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

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

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

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


cnt = 0

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

Solution (Python):
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]
  
  INFTY = 2 ** 30
  L.append(INFTY)
  R.append(INFTY)
  
  i, j = 0, 0

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

  return swap_times

def divide(A, left, right):
  

  
  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)

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

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

Solution (Python):

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)

Solution (Python):
def merge(A,left,mid,right):
    INF = 10**9
    n1 = mid - left
    n2 = right - mid
    
    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)

Solution (Python):

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)

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

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

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

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

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

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

Solution (Python):
"""
マージソートを実装する
"""
count = 0

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

    n1 = mid-left
    n2 = right-mid

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

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


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

Solution (Python):
n = int(input())

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

c = 0

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

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

mergesort(S, 0, n)

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

print(c)

Solution (Python):
import math
import sys



_exchange = 0

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

    left は A の先頭のインデックス、right は末尾のインデックスのひとつ後ろ。
    """
    if left + 1 < right:
        mid = (left  + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

def merge(A, left, mid, right):
    """ソート済みの部分列をマージする。

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

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


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

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

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

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

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


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

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

Solution (Python):
count = 0

def merge_sort(n, nums):
    if n == 1:
        return nums
    left_n = n // 2  
    left_sorted = merge_sort(left_n, nums[:left_n]) + [10**9 + 1]  
    right_n = n - left_n
    right_sorted = merge_sort(right_n, nums[left_n:]) + [10**9 + 1]  
    left_idx = 0
    right_idx = 0
    idx = 0
    sorted_list = [0] * n
    while idx < n:
        if left_sorted[left_idx] < right_sorted[right_idx]:
            sorted_list[idx] = left_sorted[left_idx]
            left_idx += 1
        else:
            sorted_list[idx] = right_sorted[right_idx]
            right_idx += 1
        idx += 1
    global count
    count += idx
    return sorted_list


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


if __name__ == "__main__":
    main()

Solution (Python):
INF = int(1e18)

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

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

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

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

Solution (Python):
INF = 10000000000

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

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

    i, j= 0, 0

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

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

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

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


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


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


if __name__ == '__main__':
    main()

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

def Merge(A, left, mid, right):
	n1 = mid - left
	n2 = right - mid
	L=[0]*(n1+1)
	R=[0]*(n2+1)
	for i in range(n1):
		L[i] = A[left + i]
	for i in range(n2):
		R[i] = A[mid + i]
	L[n1] = 10**10
	R[n2] = 10**10
	i = 0
	j = 0
	global cnt
	for k in range(left,right):
		cnt+=1
		if L[i] <= R[j]:
			A[k] = L[i]
			i+=1
		else:
			A[k] = R[j]
			j+=1

def MergeSort(A, left, right):
	if left+1 < right:
		mid = (left + right)//2
		MergeSort(A, left, mid)
		MergeSort(A, mid, right)
		Merge(A, left, mid, right)
MergeSort(a,0,n)
print(*a)
print(cnt)

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

count = 0

inf = 999999999999999999

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

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

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

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

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

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

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

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

Solution (Python):
from bisect import bisect_right as br
import sys

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

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

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

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

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

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

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

print(*a)
print(c)

Solution (Python):
A = []
ans = 0

def merge(left, mid, right):
	global A
	global ans
	n1 = mid - left
	n2 = right - mid
	l = []
	r = []
	for i in range(n1):
		l += [A[left + i]]
	for i in range(n2):
		r += [A[mid + i]]
	l += [10**18]
	r += [10**18]
	i = 0
	j = 0
	ans += right - left
	for k in range(left, right):
		if l[i] <= r[j]:
			A[k] = l[i]
			i += 1
		else:
			A[k] = r[j]
			j += 1


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

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

main()

Solution (Python):

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

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

    global count
    i, j = 0, 0

    
    

    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, n, left, right):
    if right - left > 1:
        mid = (left + right) // 2
        merge_sort(A, n, left, mid)
        merge_sort(A, n, mid, right)
        merge(A, n, left, mid, right)


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

merge_sort(A, N, 0, N)

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

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

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

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