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):
def merge(A,left,mid,right):
    global cnt
    inf=float("inf")
    L=A[left:mid]+[inf]
    R=A[mid:right]+[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 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):
n=int(input())
S=[int(i) for i in input().split()]
INF=10**10

def merge(A,l,m,r):
    cnt=0
    n1=m-l
    n2=r-m
    L,R=[0 for i in range(n1)],[0 for i in range(n2)]
    cnt=0
    L=A[l:l+n1]
    R=A[m:m+n2]
    L.append(INF)
    R.append(INF)
    i,j=0,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=0
    if l+1<r:
        m=(l+r)//2
        cnt+=mergesort(A,l,m)
        cnt+=mergesort(A,m,r)
        cnt+=merge(A,l,m,r)
    return cnt


cnt=mergesort(S,0,n)
print(*S)
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    count = 0
    INF = 1_000_000_001
    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):
        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


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

Solution (Python):

sum = 0

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

    R = [0] * (n2+1)

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

    R[n2] = 10**9

    i = 0
    j = 0
    for k in range(left, right):
        sum += 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))
print(*S)
print(sum)

Solution (Python):
import sys
sys.setrecursionlimit(10000)
num = int(input())
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [ 1e10 ]
    R = A[mid:right] + [ 1e10 ]
    i = 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)

L = [int(x) for x in input().split()]
c = mergeSort(L, 0, len(L))
print(" ".join(map(str,L)))
print(cnt)

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

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

    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

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

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

Solution (Python):
cnt=0
def merge_sort(S):
    l=len(S)
    mid=int(l/2)
    Left=S[0:mid]
    Right=S[(mid):l]
    global cnt
    
    if l>=2:
        merge_sort(Left) and merge_sort(Right)
    

    Left.append(float('inf'))
    Right.append(float('inf'))

    p=0
    q=0
    for i in range(l):
        if Left[p]<Right[q]:
            S[i]=Left[p]
            p+=1
        else:
            S[i]=Right[q]
            q+=1
    if l!=1 :
        cnt+=l
    
    return S


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

Solution (Python):

def merge(s, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = s[left:mid] + [1000000001]
    R = s[mid:right] + [1000000001]

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

def mergesort(s, 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())
count = 0
s = list(map(int, input().split()))
mergesort(s, 0, n)

for i in range(len(s)-1):
      print(s[i], end = " ")
print(s[n-1])
print(count)

Solution (Python):
cnt = 0
def merge_sort(array):
    global cnt
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left = array[:mid]
    right = array[mid:]
    cnt += len(left) + len(right)
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    list = []
    l_index, r_index = 0, 0
    while l_index < len(left) and r_index < len(right):
        if left[l_index] <= right[r_index]:
            list.append(left[l_index])
            l_index += 1
        else:
            list.append(right[r_index])
            r_index += 1
    if l_index < len(left):
        list.extend(left[l_index:])
    if r_index < len(right):
        list.extend(right[r_index:])
    
    return list

n = int(input())
S = list(map(int, input().split()))
array = merge_sort(S)
print(" ".join(map(str, array)))
print(cnt)

Solution (Python):
count=0
def merge(A,left,mid,right):
    global count
    L=A[left:mid]+[10**9+1]
    R=A[mid:right]+[10**9+1] 
    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=[int(i) for i in input().split()]
mergeSort(S,0,n)
print(*S)
print(count)

Solution (Python):
cp = 0
def m(L,R):
    global cp
    j = 0
    for l in L:
        while j < len(R) and R[j] < l:
            yield R[j]
            j += 1
        yield l
    while j < len(R):
        yield R[j]
        j += 1
    cp += len(L) + len(R)
def merge(A):
    global cp
    if len(A) == 1:
        return A
    if len(A) == 2:
        cp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A
n=int(input())
A=[int(i) for i in input().rstrip().split(" ")]
B = merge(A)
print(*B)
print(cp)

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


INF = 1000000000
idx = 0
n = int(input())
a = [int(i) for i in input().split()]
merge_sort(a,0,len(a))
print(*a)
print(idx)

Solution (Python):
def m(S, left, mid, right):
  global count
  L = S[left:mid]
  R = S[mid:right]
  L.append(1000000000)
  R.append(1000000000)
  i = 0
  j = 0
  for k in range(left,right):
    count = count + 1
    if L[i] <= R[j]:
      S[k] = L[i]
      i = i + 1
    else:
      S[k] = R[j]
      j = j + 1

def ms(S,left,right):
  if (left+1) < right:
    mid = (left+right)//2
    ms(S, left, mid)
    ms(S, mid, right)
    m(S, left, mid, right)

n = int(input())
S = [int(x) for x in input().split()]
left = 0
right = n
count = 0

ms(S,left,right)

for i in range(n):
  if i != (n-1):
    print(S[i], end = " ")
  else:
    print(S[i])
print(count)

Solution (Python):


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

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

    L=A[left:mid]+[10000000000000]
    R=A[mid:right]+[100000000000000]

    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)
d=map(str,A)
print(' '.join(d))
print(count)

Solution (Python):
import math
N=10**9 + 1
n=int(input())
a=list(map(int,input().split()))

def merge(a,left,mid,right):
    global cnt
    n=mid-left
    m=right-mid
    l=a[left:left + n]
    o=a[mid:mid + m]
    l.append(N)
    o.append(N)
    i=0
    j=0
    for k in range(left,right):
        cnt+=1
        if l[i]<=o[j]:
            a[k]=l[i]
            i+=1
        else:
            a[k]=o[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)





cnt=0
mergesort(a,0,len(a))
print(*a)
print(cnt)

Solution (Python):
def main():
    cnt = 0

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

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

    N = int(input())
    S = [int(i) for i in input().split()]
    merge_sort(S, 0, N)
    print(*S)
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
def merge(a, l, m, r):
  global count
  Left = a[l:m]
  Left.append(1e10)
  Right = a[m:r]
  Right.append(1e10)
  i, j = 0, 0
  for k in range(l, r):
    count += 1
    if Left[i] <= Right[j]:
      a[k] = Left[i]
      i += 1
    else:
      a[k] = Right[j]
      j += 1

def sort(a, l, r):
  if r-l > 1:
    m = (l+r)//2
    sort(a, l, m)
    sort(a, m, r)
    merge(a, l, m, r)
       
       
count=0
n=int(input())
a=[int(i) for i in input().split()]
sort(a, 0, n)
print(*a)
print(count)

Solution (Python):
infinity=2**35
def merge(A,left,mid,right):
  global cnt

  L=A[left:mid]
  R=A[mid:right]
  L.append(infinity)
  R.append(infinity)
  
  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())
A=list(map(int,input().split()))
cnt=0

mergeSort(A,0,n)

print(*A)
print(cnt)

Solution (Python):
global count


def merge(arr, l, mid, r):
    arr_l = list(arr[l:mid + 1])
    arr_r = list(arr[mid + 1:r + 1])
    l_index = 0
    r_index = 0
    arr_l.append(2 << 64)
    arr_r.append(2 << 64)
    global count
    for i in range(l, r + 1):
        if arr_l[l_index] <= arr_r[r_index]:
            arr[i] = arr_l[l_index]
            l_index += 1
        else:
            arr[i] = arr_r[r_index]
            r_index += 1
        count += 1


def merge_sort(arr, l, r):
    if l >= r:
        return
    mid = (l + r) // 2
    merge_sort(arr, l, mid)
    merge_sort(arr, mid + 1, r)
    merge(arr, l, mid, r)


if __name__ == '__main__':
    count = 0

    n = int(input())
    arr = list(map(int, input().split()))
    merge_sort(arr, 0, len(arr) - 1)
    for i in range(n):
        if i != n - 1:
            print(arr[i], end=' ')
        else:
            print(arr[i])
    print(count)

Solution (Python):
cnt=0
def mer(l,r):
    global cnt
    ll=len(l)
    rr=len(r)
    md=[]
    i,j=0,0
    l.append(float('inf'))
    r.append(float('inf'))
    for k in range(ll+rr):
        cnt+=1
        if l[i]<=r[j]:
            md.append(l[i])
            i+=1
        else:
            md.append(r[j])
            j+=1
    return md
def mergesort(a):
    m=len(a)
    if m<=1:
        return a
    m=m//2
    l=mergesort(a[:m])
    r=mergesort(a[m:])
    return mer(l,r)
n=int(input())
a=list(map(int, input().split()))
b=mergesort(a)
for i in range(n-1):
    print(b[i],end=" ")
print(b[n-1])
print(cnt)

Solution (Python):

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

    i=0
    j=0
    for k in range(left,right):
        if L[i]<=R[j]:
            A[k]=L[i]
            cnt=cnt+1
            i+=1
        else:     
            A[k]=R[j]
            j+=1
            cnt=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(' '.join(map(str,S)))

print(cnt)

Solution (Python):
num = 0
def marge_sort(array):
    global num
    if len(array) < 2: return array
    
    mid = len(array) // 2
    left = marge_sort(array[:mid])
    right = marge_sort(array[mid:])
    
    len_l, len_r = len(left), len(right)
    left += [float("inf")]
    right += [float("inf")]
    
    marray = [0] * (len_l + len_r)
    
    l, r = 0, 0
    for i in range(len_l + len_r):
        num += 1
        if left[l] <= right[r]:
            marray[i] = left[l]
            l += 1
        else:
            marray[i] = right[r]
            r += 1
        
    return marray

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

print(" ".join(map(str, marge_sort(a))))
print(num)

Solution (Python):
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    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
        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)

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

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
count = 0
def Merge(A, left, mid, right):
    global count
    L = A[left:mid]+[10**9]
    R = A[mid:right]+[10**9]

    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(A, 0, n)
print(' '.join([str(_) for _ in A]))
print(count)

Solution (Python):
SENTINEL = 9999999999999

count = 0

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

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

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

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

Solution (Python):
c = 0

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

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

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

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

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

    i=j=0    
    for k in range(l,r):
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i+=1
        else:
            A[k]=R[j]
            j+=1        

def mergeSort(A,l,r):
    if l+1==r:
        pass
    else:
        m=(l+r)//2
        mergeSort(A,l,m)
        mergeSort(A,m,r)
        merge(A,l,m,r)

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

mergeSort(S,0,n)

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

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

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


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


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

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

    
    

    i, j = 0, 0
    for k in range(left, right, 1):
        merge_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__':
    main()

Solution (Python):
infty = 1000000000
count = 0

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


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


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

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

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

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

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

Solution (Python):

import sys
count = 0

def merge(A, left, mid, right):
    global count
    l = A[left: mid]
    r = A[mid: right]

    l.append(float('inf'))
    r.append(float('inf'))

    i = 0
    j = 0

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


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


n = int(input())
S = [int(i) for i in sys.stdin.readline().strip().split()]

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

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

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

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


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

Solution (Python):
import sys
input = sys.stdin.readline
def marge(A, left, right, mid):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = [0] * (n1 + 1)
    R = [0] * (n2 + 1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 10 ** 9 + 1
    R[n2] = 10 ** 9 + 1
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return cnt
def margesort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = margesort(A, left, mid)
        cnt2 = margesort(A, mid, right)
        return cnt1 + cnt2 + marge(A, left, right, mid)
    return 0

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

if __name__ == '__main__': main()

Solution (Python):

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

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


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




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

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

print(count)

Solution (Python):
inf=float("inf")
def merge(a,left,mid,right):
    count=0
    n1=mid-left
    n2=right-mid
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=a[left+i]
    for i in range(n2):
        R[i]=a[mid+i]
    L[n1]=inf
    R[n2]=inf
    i=0
    j=0
    for k in range(left,right):
        count+=1
        if L[i]<=R[j]:
            a[k]=L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
    return count

def mergeSort(a,left,right):
    if left+1<right:
        mid=(left+right)//2
        return mergeSort(a,left,mid)+mergeSort(a,mid,right)+merge(a,left,mid,right)
    return 0
n=int(input())
*a,=map(int,input().split())
ans=mergeSort(a,0,n)
print(*a)
print(ans)

Solution (Python):
import sys

infty = 10**10

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

	n1 = mid -left
	n2 = right - mid

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

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

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

	i = 0
	j = 0
	cnt = 0



	for k in range(left,right):

		cnt += 1

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

	return cnt



def mergeSort(A,left,right):

	cnt = 0

	if left+1 < right:

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

	return cnt

def test():

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

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


if __name__ == "__main__":
	test()

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

cnt = 0

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

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

mergesort(0, n)

print(*S)
print(cnt)

Solution (Python):
INF = 10000000000

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

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

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

print(*A)
print(count)

Solution (Python):
class MergeSort:
    def __init__(self, array):
        self._arr = array
        self._cnt = 0

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

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

        self._cnt += right - left
        return

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

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

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

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

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

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

Solution (Python):

from collections import deque
n = int(input())
S = list(map(int, input().split()))
INFTY = 1e9 + 1

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

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

input = sys.stdin.readline

MAX = 500000
GUARD = 2000000000
cnt = 0

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

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

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

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

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

    mergeSort(S, 0, n)

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