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] 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 ≤ 109

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

Template in C
-->



Sample input:
10
8 5 9 2 6 3 7 1 10 4


Sample output:
1 2 3 4 5 6 7 8 9 10
34

Submission status: Runtime Error

Solution code:
counter = 0

def merge(L, R, left, right):
    A=[]
    L.append(float('inf'))
    R.append(float('inf'))

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

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

n = int(input())
l = list(map(int,input().split()))
ll = mergeSort(l,0,n)
print(*ll)
print(counter)

Submission status: Runtime Error

Solution code:
counter = 0

def merge(L, R, left, right):
    A = range(0,right-left)
    L.append(float('inf'))
    R.append(float('inf'))

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

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

n = int(input())
l = list(map(int,input().split()))
ll = mergeSort(l,0,n)
print(*ll)
print(counter)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
S = list(map(int,input().split()))

def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = []
    for i in range(n1+1):
        L.append(i)
    R = []
    for i in range(n2+1):
        R.append(i)
    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
    sum = 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 = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

count = 0
mergeSort(S,0,len(S))
print(*S)
print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
count = 0

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

            
def mergeSort(A,left,right):
    if left + 1 < right:
        middle = (left + right) //2
        mergeSort(A,left,middle)
        mergeSort(A,middle,right)
        merge(A,left,middle,right)
        
input()
l = list(map(int,input().split()))
mergeSort(l,0,len(l))
print(" ".join(l))
print(count)

Submission status: Runtime Error

Solution code:
import sys

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

	L = [0 for i in range(n1)]
	R = [0 for i in range(n2)]

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

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

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

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

	return num_compare


fin = open("test.txt", "r")
#fin = sys.stdin



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

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)

Submission status: Runtime Error

Solution code:
import sys

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

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

	num_compare += 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
	return num_compare

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

	return num_compare


fin = open("test.txt", "r")
#fin = sys.stdin

SENTINEL = float("inf")

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

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)

Submission status: Runtime Error

Solution code:
global cmt                                                     
cmt = 0                                                        
def Merge(left, right):                                        
    global cnt                                                 
    lst = []                                                   
    i, j = 0, 0                                                
    while i < len(left) and j < len(right):                    
        if left[i] <= right[j]:                                
            lst.append(left[i])                                
            i += 1                                             
        else:                                                  
            lst.append(right[j])                               
            j += 1                                             
    lst += left[i:]                                            
    lst += right[j:]                                           
    cmt += len(lst)                                            
                                                               
    return lst                                                 
                                                               
def MergeSort(A):                                              
    if len(A) == 1: return A                                   
    mid = len(A) / 2                                           
    left = MergeSort(A[:mid])                                  
    right = MergeSort(A[mid:])                                 
    #print left, right                                         
    sortedList = Merge(left, right)                            
    return sortedList                                          
                                                               
n = raw_input()                                                
for n in MergeSort(map(int, raw_input().split())):             
    print output, ' '                                          
print cmt

Submission status: Runtime Error

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

    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
    cnt.append(cnt1 + cnt2)
    
    
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)
        

n = int(input().rstrip())
A = list(map(int,input().split(" ")))
cnt = []
mergeSort(A, 0 , len(A), cnt)
print(" ".join(list(map(str,A))))
print(str(sum(cnt)))

Submission status: Runtime Error

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

    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
    cnt[0] = cnt[0] + cnt1 + cnt2
    
    
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)
        

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

Submission status: Runtime Error

Solution code:
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]=100000000
    R[n2]=100000000

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

count = 0
left_arr = []
right_arr = []


def merge(a, n, left, mid, right):
    n1 = mid - left
    for i in range(n1):
        left_arr[i] = a[left + 1]

    n2 = right - mid
    for i in range(n2):
        right_arr[i] = a[mid + i]

    left_arr[n1] = right_arr[n2] = 20 * 1000000

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


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


def main():
    n = int(input())
    a = [int(e) for e in input().split()]
    sorted_arr = merge_sort(a, n, 0, n)
    return " ".join(sorted_arr)


print(main())
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

infinity = 10 ** 9


def merge(ns, left, mid, right, count):
    n1 = mid - left
    n2 = right - mid
    left_ns = [e for e in range(n1)]
    right_ns = [e for e in range(n2)]

    for i in range(n1):
        left_ns[i] = ns[left + i]
    for i in range(n2):
        right_ns[i] = ns[mid + i]
    
    left_ns[n1] = infinity
    right_ns[n2] = infinity

    i = 0
    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
    return ns, count


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


n = int(input())
ns = [int(e) for e in input().split()]
left = 0
right = len(ns)
ns, count = merge_sort(ns, left, right)

print(" ".join(ns))
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

infinity = 10 ** 9
count = 0


def merge(ns, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    left_ns = [e for e in range(n1)]
    right_ns = [e for e in range(n2)]

    for i in range(n1):
        left_ns[i] = ns[left + i]
    for i in range(n2):
        right_ns[i] = ns[mid + i]
    
    left_ns[n1] = infinity
    right_ns[n2] = infinity

    i = 0
    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):
    count = 0
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(ns, left, mid)
        merge_sort(ns, mid, right)
        merge(ns, left, mid, right, count)


n = int(input())
ns = [int(e) for e in input().split()]
left = 0
right = len(ns)
merge_sort(ns, left, right)

print(" ".join(ns))
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

infinity = pow(10, 9) + 1


def merge(ns, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    # left_ns = [e for e in range(n1 + 1)]
    # right_ns = [e for e in range(n2 + 1)]
    left_ns = ns[left:mid]
    right_ns = ns[mid:right]

    # for i in range(n1):
    #     left_ns[i] = ns[left + i]
    # for i in range(n2):
    #     right_ns[i] = ns[mid + i]
    
    left_ns[n1] = infinity
    right_ns[n2] = infinity

    i = 0
    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)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1)]
    R = [0 for i in range(n2)]
    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):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j+1
    global cnt
    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 = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

Submission status: Runtime Error

Solution code:
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] = 100000001
    R[n2] = 100000001
    i = 0
    j = 0
    #global cnt
    cnt = 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
    return cnt

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

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

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    global cnt
    inf = 5000001
    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().split()))
mergeSort(A, 0, n)
print(*A)
print(cnt)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    global cnt
    inf = 50000001
    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().split()))
mergeSort(A, 0, n)
print(*A)
print(cnt)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    global cnt
    inf = 500000001
    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().split()))
mergeSort(A, 0, n)
print(*A)
print(cnt)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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] = float('inf')
    R[n2] = 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 = mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

Submission status: Runtime Error

Solution code:
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 = A[left:mid]
    R = A[mid:right]
    L[n1] = float('inf')
    R[n2] = 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))

Submission status: Runtime Error

Solution code:
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 = A[left:mid]
    R = A[mid:right]
    L[n1] = float('inf')
    R[n2] = 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))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().strip().split()))



def merge(A, left, mid, right):
    global count
    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(float("inf"))
    R.append(float("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
    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)

mergeSort(A,0,N)
ans = ""
for i in A:
    ans += str(i) + " "

print(ans)
print(count)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))



def merge(A, left, mid, right):
    global count
    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(float("inf"))
    R.append(float("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
    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)

mergeSort(A,0,N)
ans = ""
for i in A:
    ans += str(i) + " "

print(ans)
print(count)

Submission status: Runtime Error

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


def merge(A, left, mid, right):
    global count
    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(float("inf"))
    R.append(float("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
    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)

mergeSort(A,0,N)


print(" ".join(A))
print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python

def mergesort(mylist, num):
    
    len_list = len(mylist)
    center = int(len_list / 2)

    former = mylist[:center]
    len_former = len(former)
    if len_former > 1:
        mergesort(former, num)
   
    latter = mylist[center:]
    len_latter = len(latter)
    if len_latter > 1:
        mergesort(latter, num)

    temp = mylist[:]
    i = 0
    j = 0
    k = 0
    both_flag = True

    while both_flag:
        while both_flag and former[i] <= latter[j]:
            mylist[k] = former[i]
            i += 1
            k += 1
            num[0] += 1
            if i == len_former:
                both_flag = False
        while both_flag and latter[j] < former[i]:
            mylist[k] = latter[j]
            j += 1
            k += 1
            num[0] += 1
            if j == len_latter:
                both_flag = False
    
    while j < len_latter:
        mylist[k] = latter[j]
        j += 1
        k += 1
        num[0] += 1
    while i < len_former:
        mylist[k] = former[i]
        i += 1
        k += 1
        num[0] += 1

N = int(input())
S = list(map(int, input().split(" ")))
num = [0]
mergesort(S, num)
#print(S)
print(" ".join(S))
print(num[0])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????????????????????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 = 100000000

def merge(A, left, mid, right, cnt):
#    print("l:{} m:{} r:{} cnt:{}".format(left,mid,right,cnt))
    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(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()

Submission status: Runtime Error

Solution code:
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 = input()
S = list(map(int,input(),split()))
cnt=0

mergeSort(S,0,n)

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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