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):
n=int(input())
nums=list(map(int,input().split()))
count=0
def merge(nums,left,mid,right):
    global count
    inf=10**9
    L=nums[left:mid]+[inf]
    R=nums[mid:right]+[inf]
    i=0
    j=0
    for k in range(left,right):
        count+=1
        if R[j]>=L[i]:
            nums[k]=L[i]
            i+=1

        else:
            nums[k]=R[j]
            j+=1

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

merge_sort(nums,0,n)

def show(nums):
    l=len(nums)
    for i in range(l):
        if i!=l-1:
            print(nums[i],end=" ")
            
        else:
            print(nums[i])
            
show(nums)
print(count)

Solution (Python):
def merge(A,left,mid,right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    cnt += n1+n2
    L = [A[left+i] for i in range(n1)]
    R = [A[mid+i] for i in range(n2)]
    L.append(float("inf"))
    R.append(float("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

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()))
cnt = 0
mergesort(A,0,n)
print(" ".join(map(str,A)))
print(cnt)

Solution (Python):

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

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

Solution (Python):
from array import array

def readinput():
    n=int(input())
    a=array('L',list(map(int,input().split())))
    return n,a

count=0
def merge(a,left,mid,right):
    INFTY=10**9+1
    global count
    n1=mid-left
    n2=right-mid
    
    L=a[left:mid]
    L.append(INFTY)

    
    R=a[mid:right]
    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
        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)
    return

def main(n,a):
    global count
    mergeSort(a,0,n)
    return a,count

if __name__=='__main__':
    n,a=readinput()
    a,count=main(n,a)
    print(' '.join(map(str,a)))
    print(count)

Solution (Python):
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1] 
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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

def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((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()))
c = 0
mergeSort(a, 0, n)
print(" ".join(map(str, a)))
print(c)

Solution (Python):
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10) 
    r.append(10e10)
    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
    
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = math.ceil((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()))
c = 0
    
mergeSort(a, 0, n)
    
print(" ".join(map(str, a)))
print(c)

Solution (Python):
n = int(input())
S = [int(i) for i in input().split()]
infty = 10**10
cnt = 0
def merge(A, left, mid, right):
    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):
        global cnt
        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 = int((left + right)/2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
mergeSort(S, 0, len(S))
print(" ".join([str(st) for st in S]))
print(cnt)

Solution (Python):
num = int(input())
s = list(map(int, input().split()))
cnt = 0

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

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


merge_sort(s, 0, num)

print(*s)
print(cnt)

Solution (Python):
def merge(A, left, mid, right, cnt):
    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(1e10)
    R.append(1e10)

    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

    else:
        cnt.append(c)


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


def main():
    cnt = []
    _ = int(input())
    S = list(map(int, input().split()))
    mergeSort(S, 0, len(S), cnt)
    print(*S)
    print(sum(cnt))


if __name__ == "__main__":
    main()

Solution (Python):
import math

n = int(input())
A = list(map(int, input().split()))
cnt = 0
inf = 10**9



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

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

Solution (Python):
import math
count = 0
def merge(a,left,mid,right):
    global count
    
    
    L = A[left:mid]+[1e9]
    R = A[mid:right]+[1e9]
    
        
    
        
    
    
    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+=1
        
def mergesort(A,l,r):
    if (l+1) < r:
        mid = math.floor((l+r)/2)
        mergesort(A,l,mid)
        mergesort(A,mid,r)
        merge(A,l,mid,r)
N = int(input())
A = [int(x) for x in input().split(" ")]
A.append(1e9)
mergesort(A,0,N)
for i in range(len(A)):
    if i < len(A)-2:
        print(A[i],end=" ")
    else:
        print(A[i])
        break

print(count)

Solution (Python):
import sys
n = int(input())
sort_list = list(map(int,input().split()))

cnt = []
def merge(A, left,mid,right):
    n1 = mid -left
    n2 = right - mid
    L = [i for i in A[left : left + n1]]
    R = [i for i in A[mid : mid + n2]]
    L.append(sys.maxsize)
    R.append(sys.maxsize)

    i = 0
    j = 0
    c = 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
        c += 1

    cnt.append(c)

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(sort_list, 0, len(sort_list))
print(' '.join([str(i) for i in sort_list]))
print(sum(cnt))

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

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)

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

  L = S[left:mid] + [10**10]
  R = S[mid:right] + [10**10]

  i,j = 0,0

  global cnt
  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

mergeSort(S, 0, len(S))
print (' '.join(map(str,S)))
print (cnt)

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

cnt = 0
INF = 10000000000

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

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

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

print(*A)
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 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 = 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()))
count = 0
mergeSort(A, 0, n)

print(*A)
print(count)

Solution (Python):
count = [0]

def merge(A, left, right, mid, count):
    lstl = A[left: mid] + [5000000000]
    lstr = A[mid: right] + [5000000000]
    pl = 0
    pr = 0
    for _ in range(left, right):
        if lstl[pl] < lstr[pr]:
            A[left + pl + pr] = lstl[pl]
            pl += 1
            count[0] += 1
        else:
            A[left + pr + pl] = lstr[pr]
            pr += 1
            count[0] += 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, right, mid, count)

import sys
input = sys.stdin.readline

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

merge_sort(S, 0, n)
print(" ".join(map(str, S)))
print(count[0])

Solution (Python):
count = 0

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

  n1 = int(mid - left)
  n2 = int(right - mid)

  l = array[left:mid]
  r = array[mid:right]
  
  l.append(9999999999)
  r.append(9999999999)

  i, j = 0, 0

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

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

n = int(input())
array = [int(i) for i in input().split()]
mergeSort(array, 0, n)
print(*array)
print(count)

Solution (Python):
def merge(A, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    L = [0 for e in range(n1+1)]
    R = [0 for e in range(n2+1)]
    L = A[left:mid] + [10 ** 9]
    R = A[mid:right] + [10 ** 9]
    i = 0
    j = 0
    for k in range(left,right):
        if L[i] <= R[j]:
          A[k] = L[i]
          i = i + 1
        else:
          A[k] = R[j]
          j = j + 1
    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)

if __name__ == "__main__":
    n = int(input())
    S = [int(e) for e in input().split()]
    c = 0
    mergeSort(S,0,n)
    print(*S)
    print(c)

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

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

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

Solution (Python):
import math

def merge(A, left, mid, right, cnt):
    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] = math.inf
    R[n2] = math.inf
    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 A, cnt

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, cnt = merge(A, left, mid, right, cnt)
    return A, cnt
        
n = int(input())
S = list(map(int,input().split()))

S_out, cnt_out = mergeSort(S,0,len(S),0)

S_str = list(map(str,S))
print(" ".join(S_str))
print(str(cnt_out))

Solution (Python):


INF = 10000000000

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

    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    i,j = 0,0
    for k in range(left,right):
        ctr += 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()))
ctr = 0

mergeSort(A,0,n)

print(*A)
print(ctr)

Solution (Python):
cnt = 0
INF = pow(10, 18)

def merge(A, left, mid, right):
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        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, n)
print(*s)
print(cnt)

Solution (Python):
N=int(input())
num_list=list(map(int,input().split(" ")))
MAX=500000
L=[None]*((MAX)//2+2)
R=[None]*((MAX)//2+2)
def merge(A,left,mid,right):
    cnt=0
    n1=mid-left
    n2=right-mid


    for i in range(n1):
        L[i]=A[i+left]
    for i in range(n2):
        R[i]=A[i+mid]
    L[n1]=(10**9+1)
    R[n2]=(10**9+1)
    j,k=0,0
    for i in range(left,right):
        cnt+=1
        if L[j]<=R[k]:
            A[i]=L[j]
            j+=1
        else:
            A[i]=R[k]
            k+=1
    return cnt
def mergesort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        cntL=mergesort(A,left,mid)
        cntR=mergesort(A,mid,right)
        return merge(A,left,mid,right)+cntL+cntR
    return 0
cnt=mergesort(num_list,0,N)
print(*num_list)
print(cnt)

Solution (Python):
n=int(input())
A=tuple(map(int, input().split()))
cnt=0

def merge_sort(A,cnt):
    m=len(A)
    if m == 1:
        return A,cnt
    else:
        mid=(m+1)//2
        A1=tuple(A[:mid])
        A2=tuple(A[mid:])
        A1,cnt=merge_sort(A1,cnt)
        A2,cnt=merge_sort(A2,cnt)
        n1=len(A1)
        n2=len(A2)
        i1=0
        i2=0
        ans=[0]*(n1+n2)
        j=0
        while j < n1+n2:
            if i1 == n1:
                ans[j]=A2[i2]
                i2+=1
                cnt+=1
            elif i2 == n2:
                ans[j]=A1[i1]
                i1+=1
                cnt+=1
            elif A1[i1] < A2[i2]:
                ans[j]=A1[i1]
                i1+=1
                cnt+=1
            else:
                ans[j]=A2[i2]
                i2+=1
                cnt+=1
            j += 1
        return ans,cnt

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

Solution (Python):




























def count(l, r):
    cnt = 0
    if l + 1 < r:
        mid = (l + r) >> 1
        cnt += count(l, mid)
        cnt += count(mid, r)
        cnt += r - l
    return cnt

cnt = count(0, int(input()))
arr = list(map(int, input().split()))
arr.sort()
print(*arr)
print(cnt)

Solution (Python):
N = int(input())
S = [int(s) for s in input().split()]

snt = 10 ** 9 + 1
cnt = 0



def merge(S, N, left, mid, right):
    global cnt
    
    
    
    
    
    
    
    L = S[left:mid] + [snt]
    R = S[mid:right] + [snt]
    i, j = 0, 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 merge_sort(S, N, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        merge_sort(S, N, left, mid)
        merge_sort(S, N, mid, right)
        merge(S, N, left, mid, right)

merge_sort(S, N, 0, N)

print(*S)
print(cnt)

Solution (Python):
n = int(input())
S = list(map(int, input().split()))
c = 0


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


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


merge_sort(0, n)

print(*S)
print(c)

Solution (Python):


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

def merge_sort(arr, left, right):
	
	global cnt
	if right - left == 1:
		return 
	mid = left + (right - left) // 2
	merge_sort(arr, left, mid)
	merge_sort(arr, mid, right)
	a = [arr[i] for i in range(left, mid)] \
		+ [arr[i] for i in range(right - 1, mid - 1, -1)]
	iterator_left = 0
	iterator_right = len(a) - 1
	for i in range(left, right):
		cnt += 1
		if a[iterator_left] <= a[iterator_right]:
			arr[i] = a[iterator_left]
			iterator_left += 1
		else:
			arr[i] = a[iterator_right]
			iterator_right -= 1

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

Solution (Python):
import math

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

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

  global  count

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


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


mergeSort(A,0,n)
x = list(map(str,A))
print(" ".join(x))
print(count)

Solution (Python):
comparison = 0

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

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

    i = 0
    j = 0

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
c = 0

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

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

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
MAXINT = 1000000001

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


def merge(A, l, m, r, cnt):
  n1 = m - l
  n2 = r - m
  L = [A[i] for i in range(l, l+n1)]
  R = [A[i] for i in range(m, m+n2)]
  L.append(MAXINT)
  R.append(MAXINT)
  i = 0
  j = 0
  for k in range(l,r):
    cnt += 1
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  return cnt


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

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

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

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

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

mergeSort(S, 0, n)
print(" ".join(map(str, S)))
print(count)

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


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


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


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

Solution (Python):


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


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


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

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

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

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

mergeSort(S, 0, n)

print(*S)
print(count)

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

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

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

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


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


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

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


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


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

Solution (Python):
import sys,collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = 0
def merge(a,left,mid,right):
  n1 = mid - left
  n2 = right - mid
  L = a[left:mid]
  R = a[mid:right]
  L.append(float("inf"))
  R.append(float("inf"))
  i = 0
  j = 0
  for k in range(left,right):
    global c
    c += 1
    if L[i] <= R[j]:
      a[k] = L[i]
      i += 1
    else:
      a[k] = R[j]
      j += 1

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

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

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 = 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):
count = 0

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

    global count

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

    i = j = 0

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

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

    MergeSort(arr, 0, n)

    print(*arr)
    print(count)

Main()

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

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

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

    i = 0
    j = 0

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

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

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

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

Solution (Python):
inf = 10**9 + 7


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


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


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