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):
import sys
from typing import List
import math

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


def merge(A: List[int], left: int, mid: int, right: int) -> None:
    global hikaku
    
    

    
    
    left_list = A[left:mid]
    right_list = A[mid:right]
    left_list.append(sys.maxsize)
    right_list.append(sys.maxsize)

    i = 0  
    j = 0  
    for k in range(left, right):
        hikaku += 1
        if left_list[i] <= right_list[j]:
            A[k] = left_list[i]
            i += 1
        else:
            A[k] = right_list[j]
            j += 1


def merge_sort(A: List[int], left: int, right: int) -> int:
    if left + 1 < right:
        mid = math.floor((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


merge_sort(S, 0, len(S))
print(' '.join(map(str, S)))
print(hikaku)

Solution (Python):


"""
マージソート
・再帰で全部分割してから統合
"""

import sys
def input(): return sys.stdin.readline().strip()

N = int(input())
aN = list(map(int, input().split()))
ans = 0

def merge(l, m, r):
    
    global ans    

    
    L = aN[l:m]
    R = aN[m:r]
    
    L.append(float('inf'))
    R.append(float('inf'))

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

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

merge_sort(0, N)
print(*aN)
print(ans)

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


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

    a1 = a[left:mid] + [math.inf]
    a2 = a[mid:right] + [math.inf]

    i = j = 0
    for k in range(left, right):
        if a1[i] <= a2[j]:
            a[k] = a1[i]
            i += 1
        else:
            a[k] = a2[j]
            j += 1
        count += 1

    return count


def merge_sort(a, left, right):
    if left + 1 >= right:
        return 0

    count = 0
    mid = (left + right) // 2
    count += merge_sort(a, left, mid)
    count += merge_sort(a, mid, right)
    count += merge(a, left, mid, right)
    return count


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().split()]
count = merge_sort(a, 0, len(a))

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

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

cnt = 0
n = int(input())
A = list(map(int, input().strip().split()))
mergeSort(A, 0, n)
print(*A)
print(cnt)

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


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

print(' '.join(str(a) for a in A))
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    INF = 1000000001

    L = A[left:left + n1] + [INF]
    R = A[mid:mid + n2] + [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
    return right - left
            
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

n = int(input())
A = list(map(int, input().split()))
left = 0
right = n
cnt = mergeSort(A, left, right)
print(' '.join(map(str, A)))
print(cnt)

Solution (Python):
import math
import sys

def merge(nums, left, mid, right):
    sentiel = sys.maxsize

    lefts = [nums[left+i] for i in range(mid - left)]
    lefts.append(sentiel)

    rights = [nums[mid+i] for i in range(right - mid)]
    rights.append(sentiel)

    l = 0
    r = 0
    cnt = 0

    for k in range(left, right):
        if lefts[l] <= rights[r]:
            nums[k] = lefts[l]
            l += 1
        else:
            nums[k] = rights[r]
            r += 1
        cnt += 1

    return nums, cnt

def mergeSort(nums, left, right):
    if right - left <= 1:
        return nums, 0

    mid = left + math.ceil((right - left)/2)

    nums, cntl = mergeSort(nums, left, mid)
    nums, cntr = mergeSort(nums, mid, right)

    nums, cnt  = merge(nums, left, mid, right)

    return nums, cnt+cntl+cntr

def main():
    n = int(input())
    nums = [int(x) for x in input().split(' ')]

    snums, cnt = mergeSort(nums, 0, n)

    print(' '.join([str(x) for x in snums]), cnt, sep="\n")

if __name__ == '__main__':
    main()

Solution (Python):
def swap(list,i,j,count):
    if(list[j]<list[i]):
        list[i],list[j]=list[j],list[i]
        return 1
    return 0

def merge(list,left1,left2,right2,count):
    i=left1
    j=left2
    tmp_list=[]
    while(1):
        if(list[i] <=list[j]):
            tmp_list.append(list[i])
            i+=1
        else:
            tmp_list.append(list[j])
            j+=1
        if(i==left2):
            for k in range(j,right2):
                tmp_list.append(list[k])
            break
        if(j==right2):
            for k in range(i,left2):
                tmp_list.append(list[k])
            break
    for k in range(left1,right2):
        list[k]=tmp_list[k-left1]
    count[0]+=right2-left1
    

                
                
    
        



def merge_sort(list,left,right,count):
    if(right  == left ):
        return None
    if(left+1 == right):
        swap(list,left,right,count)
        count[0]+=2
    else:
        mid=(left + right)//2
        merge_sort(list,left,mid,count)
        merge_sort(list,mid+1,right,count)
        merge(list,left,mid+1,right+1,count)
        

n=int(input())
data=list(map(int,input().split()))
count=[0]
merge_sort(data,0,n-1,count)
print(" ".join(list(map(str,data))))
print(count[0])

Solution (Python):
def mergesort(n_list, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right)/2)
        mergesort(n_list, left, mid)
        mergesort(n_list, mid, right)
        merge(n_list, left, mid, right)

def merge(n_list, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l_list = n_list[left:mid]
    r_list = n_list[mid:right]
    l_list.append(10e10)
    r_list.append(10e10)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if l_list[i] < r_list[j]:
            n_list[k] = l_list[i]
            i += 1
        else:
            n_list[k] = r_list[j]
            j += 1

        
        

import math
n = int(input())
n_list = list(map(int, input().split()))
c = 0
mergesort(n_list, 0, n)
print(" ".join(map(str, n_list)))
print(c)

Solution (Python):
import sys

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]+[SENTINEL]
    R = A[mid:mid+n2]+[SENTINEL]
    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):
    global ncomp
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
        ncomp += right-left
ncomp=0
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
SENTINEL = max(s)+1
MergeSort(s, 0, n)
print(' '.join(map(str,s)))
print(ncomp)

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

def marge(A, p, q, r):
    
    
    L, R = A[p: q], A[q: r]
    global c
    L.append(int(10E10))
    R.append(int(10E10))

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

def marge_sort(A, p, r):
    if p + 1 < r:
        q = math.ceil((p + r) / 2)
        marge_sort(A, p, q)
        marge_sort(A, q, r)
        marge(A, p, q, r)

marge_sort(S, 0, len(S))
print(' '.join(map(str, S)))
print(c)

Solution (Python):



from math import inf

c = 0

def merge(A, left, mid, right):
    global c
    
    
    L = A[left:mid]; L.append(inf)
    R = A[mid:right]; R.append(inf)
    
    
    i = iter(L); l = next(i)
    j = iter(R); r = next(j)
    for k in range(left, right):
        
        c += 1
        if l < r:
            A[k] = l
            l = next(i)
        else:
            A[k] = r
            r = next(j)

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

def main():
    n = int(input())
    S = [int(x) for x in input().split()]
    merge_sort(S, 0, n)
    print(*S)
    print(c)

main()

Solution (Python):
from collections import deque


def merge(a, l, m, r):
    global c
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(10e10)
    rl.append(10e10)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    c += r - l


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


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

Solution (Python):
cnt = 0

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

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

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

Solution (Python):
import sys
import math

f = sys.stdin
n = int(f.readline().split()[0])
A = list(map(int, f.readline().split()[:n]))

COUNT = 0

def Merge(A, left, mid, right):
    global COUNT
    if left == right:
        return
    n1 = mid - left
    n2 = right - mid
    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):
        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)

Merge_Sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(COUNT)

Solution (Python):
count = 0

def merge(a, left, mid, right):
    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 = 0
    j = 0
    global count
    count += right - left
    for k in range(left, right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1


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


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

mergeSort(a, 0, n)

print(' '.join([str(v) for v in a]))
print(count)

Solution (Python):
c = 0
def m(L,R):   
    global c
    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
    c += len(L) + len(R)
    
def merge(A):
    global c
    if len(A) == 1:
        return A
    if len(A) == 2:
        c += 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())
nlist = list(map(int,input().split()))
A = merge(nlist)  
print(*A)
print(c)

Solution (Python):
import sys
count = 0

def merge_sort(arr):
	merge_sort_(arr, 0, len(arr))

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

def merge(arr, left, mid, right):
	global count
	
	n1 = mid - left
	n2 = right - mid
	







	
	L = arr[left:left + n1]
	R = arr[mid:mid + n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)

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

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





print(count)

Solution (Python):

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

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