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


    








    



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

    cnt1 = 0
    cnt2 = 0
    
    for k in range(left, right):
        if L[cnt1] <= R[cnt2]:
            A[k] = L[cnt1]
            cnt1 += 1
        else:
            A[k] = R[cnt2]
            cnt2 +=  1
    
    global cnt
    cnt += cnt1 + cnt2
    
    
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().rstrip())
A = list(map(int,input().split(" ")))
cnt = 0
mergeSort(A, 0 , len(A))
print(" ".join(list(map(str,A))))
print(str(cnt))

Solution (Python):


infinity = pow(10, 9) + 1


def merge(ns, left, mid, right):
    global count
    left_ns = ns[left:mid] + [infinity]
    right_ns = ns[mid:right] + [infinity]
    i = j = 0
    for k in range(left, right):
        count += 1
        if left_ns[i] <= right_ns[j]:
            ns[k] = left_ns[i]
            i += 1
        else:
            ns[k] = right_ns[j]
            j += 1


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


n = int(input())
ns = [int(e) for e in input().split()]


left = 0
right = len(ns)
count = 0
merge_sort(ns, left, right)

print(*ns)
print(count)

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


def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (right + left) // 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()))
    cnt = 0
    mergeSort(S, 0, n)
    print(*S)
    print(cnt)

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


import sys
import os
import math


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

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

    S = A[left:mid]
    T = A[mid:right]
    S.append(float('inf'))
    T.append(float('inf'))

    s_i = 0
    t_i = 0
    for i in range(right - left):
        cnt += 1
        if S[s_i] < T[t_i]:
            A[left + i] = S[s_i]
            s_i += 1
        else:
            A[left + i] = T[t_i]
            t_i += 1


def merge_sort(A, left, right):
    if left + 1 == right:
        
        return
    else:
        
        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(*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(float('inf'))
    R.append(float('inf'))
    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
    return cnt

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)
    else:
        return 0

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

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

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

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


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 merge(A, left, mid, right):
    global counter
    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
        counter += 1


n = int(input())
A = list(map(int, input().split()))
counter = 0
inf = float("inf")

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

Solution (Python):
def merge(a, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = a[left:left + n1] + [SENTINEL]
    R = a[mid:mid + n2] + [SENTINEL]
    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 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)
 
SENTINEL = 1000000001
n = int(input())
a = list(map(int, input().strip().split()))
count = 0
merge_sort(a, 0, len(a))
print(' '.join(map(str, a)))
print(count)

Solution (Python):
def main():
    n = input()
    A = map(int,raw_input().split())

    c = mergeSort(A,0,n)

    for i in range(n-1):
        print A[i],
    print A[-1]
    print c

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

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


if __name__ == "__main__":
    main()

Solution (Python):
SENTINEL = 2000000000
L = R = [0]
cnt = 0
def merge(A, n, left, mid, right):
    L = A[left:mid] + [SENTINEL]
    R = A[mid:right] + [SENTINEL]
    i = 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, n, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, n, left, mid)
        mergeSort(A, n, mid, right)
        merge(A, n, left, mid, right)
n = int(input())
A = [int(i) for i in input().split()]
mergeSort(A, n, 0, n)
print(*A)
print(cnt)

Solution (Python):
INF = 10000000000


def merge(A, left, mid, right):
    global num
    leftA = A[left:mid]
    rightA = A[mid:right]
    leftA.append(INF)
    rightA.append(INF)
    l = 0
    r = 0
    for i in range(left, right):
        num += 1
        if leftA[l] <= rightA[r]:
            A[i] = leftA[l]
            l += 1
        else:
            A[i] = rightA[r]
            r += 1


def mergeSort(A, left, right):
    if right - left < 2:
        return
    mid = left + (right - left) // 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()))
    num = 0
    mergeSort(S, 0, len(S))
    print(" ".join(map(str, S)))
    print(num)

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


if __name__=='__main__':
    n = int(input())
    A = list(map(int, input().strip().split()))
    count = 0
    merge_sort(A, 0, n)
    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(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
    global count
    count += 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)

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

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


def merge_sort(S, left = 0, right = 500000):
	right = min(len(S),right)
	if left+1 < right:
		mid = (left+right) // 2
		merge_sort(S, left, mid)
		merge_sort(S, mid, right)
		merge(S, left, mid, right)


if __name__ == '__main__':
	n = int(input())
	S = [int(s) for s in input().split()]
	cnt = 0
	merge_sort(S)
	print(*S)
	print(cnt)

Solution (Python):


"""
?????????????????????Merge Sort??????????????±??????????????\??????????????¢?????´???????????§???
?¬?????????????????£????????????¨?????§????????????

merge(A, left, mid, right)
  n1 = mid - left;
  n2 = right - mid;
  L[0...n1], R[0...n2] ?????????
  for i = 0 to n1-1
    L[i] = A[left + i]
  for i = 0 to n2-1
    R[i] = A[mid + i]
  L[n1] = INFTY
  R[n2] = INFTY
  i = 0
  j = 0
  for k = left to right-1
    if L[i] <= R[j]
      A[k] = L[i]
      i = i + 1
    else 
      A[k] = R[j]
      j = j + 1

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

n ????????´??°???????????°??? S ????????????????????????????????£???????????????????????§
???????????´?????????????????°????????????????????????????????????
?????????merge???????????????????????°????????°?????±????????????????????????
"""

MAX = 1000000001

def merge(A, left, mid, right, cnt):
    n1 = mid - left
    n2 = right - mid









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

    L.append(MAX)
    R.append(MAX)


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

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

def main():
    """ ????????? """
    n = int(input())
    S = list(map(int,input().split()))
    cnt = mergeSort(S, 0, n, 0)
    print(" ".join(map(str,S)))
    print(cnt)

if __name__ == '__main__':
    main()

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

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
count = 0

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

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = int((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 count

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

mergeSort(S,0,n)

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

Solution (Python):
global_count = 0

def sort(a):
    return merge_sort(a)

def merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    lo = 0
    hi = n
    med = (lo+hi)/2
    left = merge_sort(a[lo:med])
    right = merge_sort(a[med:hi])
    return merge(left, right)

def merge(a,b):
    global global_count
    c = []
    na = len(a)
    nb = len(b)
    i = 0
    j = 0
    while i < na and j < nb:
        if a[i] < b[j]:
            global_count += 1
            c.append(a[i])
            i += 1
        else:
            global_count += 1
            c.append(b[j])
            j += 1

    if i == na:
        while j < nb:
            global_count += 1
            c.append(b[j])
            j += 1
    if j == nb:
        while i < na:
            global_count += 1
            c.append(a[i])
            i += 1

    return c

n = int(raw_input())
a = map(int, raw_input().split(' '))
c = sort(a)
print ' '.join(map(str, c))
print global_count

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

mergeSort(S,0,n)

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

Solution (Python):
def merge(A, l, m, r):
    L = A[l:m] + [10 ** 9 + 1]
    R = A[m:r] + [10 ** 9 + 1]
    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
    global cnt
    cnt += r - l

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

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

Solution (Python):
cnt = 0
def merge(A,left,mid,right):
	'''n1 = mid - left
	n2 = right - mid
	L = []
	R = []
	for i in range(0,n1):
		L.append(A[left+i])

	for i in range(0,n2):
		R.append(A[mid+i])
	L.append(1000000001)
	R.append(1000000001)
	'''
	L = A[left:mid]+[1000000001]
	R = A[mid:right]+[1000000001]

	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)


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

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

def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [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 += right - left

def mergeSort(a, left, right):
    if left + 1 < right:
        mid = right + (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):

import sys


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    l_len = len(L)
    r_len = len(R)
    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if l_len <= i:
            lst[k] = R[j]
            j += 1
        elif r_len <= j:
            lst[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            lst[k] = L[i]
            i += 1
        else:
            lst[k] = R[j]
            j += 1
    return cnt


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        cnt = mergeSort(lst, left, mid)
        cnt += mergeSort(lst, mid, right)
        return merge(lst, left, mid, right) + cnt
    else:
        return 0


if __name__ == "__main__":
    lst = [val.split() for val in sys.stdin.read().splitlines()]
    data = [int(n) for n in lst[1]]
    cnt = mergeSort(data, 0, int(lst[0][0]))
    print(" ".join([str(n) for n in data]))
    print(cnt)

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(1000000001)
	R.append(1000000001)
	i = 0
	j = 0
	for k in xrange(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)
	return A

n = int(raw_input())
S = map(int, raw_input().split())

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

for i in xrange(len(A)-1):
	print(A[i]),
print A[len(A) - 1]
print cnt

Solution (Python):
n = int(input())
S = list(map(int, input().split()))
SENTINEL = 10 ** 9 + 1
count = 0

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

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)

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

Solution (Python):
n = int(input())
S = list(map(int, input().split()))
SENTINEL = 10 ** 10 + 1
count = 0

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

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)

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

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

Solution (Python):
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):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  count += 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)

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

Solution (Python):


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

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

Solution (Python):
cnt = 0

def merge(A, left, mid, right):
    global cnt
    L, R = A[left:mid], A[mid:right]
    L.append(float('inf'))
    R.append(float('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 left+1 < right:
        mid = (left + right) / 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def main():
    global cnt
    n = int(raw_input())
    A = map(int, raw_input().split())

    cnt = 0
    merge_sort(A, 0, n);

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


main()

Solution (Python):

def merge(a, left, mid, right):
    n1 = mid-left
    n2 = right - mid

    left_list = [a[left + i] for i in range(n1)]
    right_list = [a[mid + i] for i in range(n2)]
    left_list.append(1000000007)
    right_list.append(1000000007)

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


def merge_sort(a, left, right, counter):
    if left+1 < right:
        mid = (left + right)//2
        counter1 = merge_sort(a, left, mid, counter)[1]
        counter2 = merge_sort(a, mid, right, counter)[1]
        counter += merge(a, left, mid, right)
        counter += counter1
        counter += counter2
    return a, counter


if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    merge_counter = 0
    S, merge_counter = merge_sort(S[:], 0, len(S), merge_counter)

    print(' '.join(map(str, S)))
    print(merge_counter)

Solution (Python):
def mergeArray(a,b,bLength,c,cLength):
    global count
    apos,bpos,cpos=(0,0,0)
    while bpos<bLength and cpos<cLength:
        if b[bpos]<=c[cpos]:
            a[apos]=b[bpos]
            bpos+=1
        else:
            a[apos]=c[cpos]
            cpos+=1
        apos+=1
        count+=1
    
    while bpos<bLength:
        a[apos]=b[bpos]
        apos+=1
        bpos+=1
        count+=1
    
    while cpos<cLength:
        a[apos]=c[cpos]
        apos+=1
        cpos+=1
        count+=1

def mergeSort(a,aLength):
    b=[]
    c=[]
    if aLength>=2:
        b=a[:aLength//2]
        c=a[aLength//2:]
        mergeSort(b,len(b))
        mergeSort(c,len(c))
    mergeArray(a,b,len(b),c,len(c))

count=0
aLength=int(input())
a=list(map(int,input().split()))
mergeSort(a,aLength)
print(*a)
print(count)

Solution (Python):
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left: left + n1] + [INF]
    R = A[mid: mid + n2] + [INF]
    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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(*S)
print(cnt)

Solution (Python):
INF = float("inf")
cnt = 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
    global cnt
    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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(*S)
print(cnt)

Solution (Python):


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

    L[n1] = float('inf')
    R[n2] = float('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)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

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

Solution (Python):


def merge(A, left, mid, right):
    global cnt
    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
    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)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

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

Solution (Python):
count = 0

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

    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 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 = [int(x) for x in input().split()]

    mergeSort(a, 0, n)

    print(*a)
    print(count)