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:
n = int(input())
S = list(map(int, input().split()))
SENTINEL = 10 ** 9 + 1
count = 0

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

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)

Submission status: Runtime Error

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

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

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)

Submission status: Runtime Error

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

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

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)

Submission status: Runtime Error

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

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

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)

Submission status: Runtime Error

Solution code:
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
    for k in range(left, right):
        if(L[i] <= R[i]):
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1
    count += right - left

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)

Submission status: Runtime Error

Solution code:
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[i]):
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1
    count += right - left

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)

Submission status: Runtime Error

Solution code:
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
    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

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)

Submission status: Runtime Error

Solution code:
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

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)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
count = 0
def merge(A, left, mid, right):
  n1 = mid - left
  n2 = right - mid
  L = A[left:mid] + [float('inf')]
  R = A[mid:right] + [float('inf')]
  
  i = 0
  j = 0

  for k in range(left, right):
    if L[i] <= R[i]:
      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()))
mergeSort(A, 0, N)
print(*A)
print(count)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
  n1 = mid - left
  n2 = right - mid
  L = A[left:mid] + [float('inf')]
  R = A[mid:right] + [float('inf')]
  
  i = 0
  j = 0

  for k in range(left, right):
    if L[i] <= R[i]:
      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)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
  global count
  n1 = mid - left
  n2 = right - mid
  L = A[left:mid] + [float('inf')]
  R = A[mid:right] + [float('inf')]
  
  i = 0
  j = 0

  for k in range(left, right):
    if L[i] <= R[i]:
      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)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
  global count
  n1 = mid - left
  n2 = right - mid
  L = A[left:mid] + [10**9]
  R = A[mid:right] + [10**9]
  
  i = 0
  j = 0

  for k in range(left, right):
    if L[i] <= R[i]:
      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)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
  global count
  n1 = mid - left
  n2 = right - mid
  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[i]:
      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)

Submission status: Runtime Error

Solution code:
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[i]:
      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)

Submission status: Runtime Error

Solution code:
def merge(left, right):
?? ?? if len(left) == 0:
?? ?? ?? ?? return right
?? ?? elif len(right) == 0:
?? ?? ?? ?? return left
?? ?? elif left[0] < right[0]:
?? ?? ?? ?? return [left[0]] + merge(left[1:],right)
?? ?? else:
?? ?? ?? ?? return [right[0]] + merge(left,right[1:])

def merge_sort(sub):
?? ?? n = len(sub)
?? ?? if n == 1:
?? ?? ?? ?? return sub[0]
?? ?? for i in range(int(n/2)):
?? ?? ?? ?? sub[i] = merge(sub[i], sub[i+1])
?? ?? ?? ?? sub.pop(i+1)
?? ?? return merge_sort(sub)

n = input()
inp = input()
while inp != '':
?? ?? l = inp

l = list(l.split(' '))
sub = []
for i in range(int(n)):
?? ?? sub.append([int(l[i])])
merge_sort(sub)

Submission status: Runtime Error

Solution code:
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
c=-int(input())
print(*d(list(map(int,input().split()))))
print(c-n)

Submission status: Runtime Error

Solution code:
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
def s():
 c=-int(input())
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:s()

Submission status: Runtime Error

Solution code:
def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def run():
    _ = int(input())  # flake8: noqa

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

    (c, s) = merge_sort(li)
    print(" ".join([str(i) for i in s]))
    print(c)


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

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

def merge(a, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    
    l = a[left:n1]
    r = a[mid:n2]
    
    l.append(10**10)
    r.append(10**10)
    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
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)

Submission status: Runtime Error

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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    for i,j in enumerate(A):
        if i == n-1:
            print(j)
        else:
            print(j,end=" ")
    print(count)

Submission status: Runtime Error

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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    for i,j in enumerate(A):
        if i == n-1:
            print(j)
        else:
            print(j,end=" ")
    print(count)

Submission status: Runtime Error

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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    merge_sort(A,0,n)
    for i,j in enumerate(A):
        if i == n-1:
            print(j)
        else:
            print(j,end=" ")
    print(count)

Submission status: Runtime Error

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    L=[i for i in range(n1)]
    R=[i 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.append(100000001)
    R.append(100000001)
    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+=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) 

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

Submission status: Runtime Error

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    R=[]
    L=[]
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000001)
    R.append(100000001)
    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+=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) 

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

Submission status: Runtime Error

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    R=[]
    L=[]
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(10000001)
    R.append(10000001)
    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+=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) 

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

Submission status: Runtime Error

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    n1=mid - left
    n2=right - mid
    R=[]
    L=[]
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000001)
    R.append(100000001)
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def 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().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)

Submission status: Runtime Error

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[100000000]
    R=A[mid:right]+[10000000]
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count+=1
def 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().split()))
    merge_sort(A,0,n)
    print(*A)
    print(count)

Submission status: Runtime Error

Solution code:
#include<iostream>
using namespace std;
#define INFTY 2000000000
int count=0;
void merge(int A[],int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int *L=new int[n1+1];
  int *R=new int[n2+1];
  for(int i=0;i<n1;i++){
    L[i]=A[left+i];
  }
  for(int i=0;i<n2;i++){
    R[i]=A[mid+i];
  }
  L[n1]=INFTY;
  R[n2]=INFTY;
  int i=0;
  int j=0;
  for(int k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
    count++;
  }
  delete[] L;
  delete[] R;
}
void mergeSort(int A[],int left,int right){
  if(left+1>=right)
    return;
  int mid=(left+right)/2;
  mergeSort(A,left,mid);
  mergeSort(A,mid,right);
  merge(A,left,mid,right);
}

int main(){
  int n;
  cin>>n;
  int A[10];
  for(int i=0;i<n;i++){
    cin>>A[i];
  }
  mergeSort(A,0,n);
  for(int i=0;i<n-1;i++){
    cout<<A[i]<<' ';
  }
  cout<<A[n-1]<<endl;
  cout<<count<<endl;
}

Submission status: Runtime Error

Solution code:
global cnt
cnt=0

def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    #L=[0 for i in range(n1+1)]
    #R=[0 for i in range(n2+1)]
    L=[]
    R=[]
    for i in range(max(n1,n2)):
        if i<n1:
            L.append(A[left+i])
        if i<n2:
            R.append(A[mid+j])
    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=i+1
            cnt+=1
        else:
            A[k]=R[j]
            j=j+1
            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(*S)
print(cnt)

Submission status: Runtime Error

Solution code:
global cnt
cnt=0

def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    #L=[0 for i in range(n1+1)]
    #R=[0 for i in range(n2+1)]
    L=[]
    R=[]
    for i in range(n1):
            L.append(A[left+i])
    for i in range(n2):
            R.append(A[mid+j])
    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=i+1
            cnt+=1
        else:
            A[k]=R[j]
            j=j+1
            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(*S)
print(cnt)

Submission status: Runtime Error

Solution code:
global cnt
cnt=0

def merge(A,left,mid,right):
    global cnt
    n1=mid-left
    n2=right-mid
    #L=[0 for i in range(n1+1)]
    #R=[0 for i in range(n2+1)]
    L=[]
    R=[]
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+j])
    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=i+1
            cnt+=1
        else:
            A[k]=R[j]
            j=j+1
            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(*S)
print(cnt)

Submission status: Runtime Error

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

cnt=[0]
mergeSort(S,0,n)
print(*S)
print(cnt[0])

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <sstream>
void merge(int A[],int left,int mid,int right){
  int n1,n2;
  n1=mid-left;
  n2=right-mid;
  int L[n1]={0};
  int R[n2]={0};
  for(int i=0;i<n1;i++){
    L[i]=A[left+i];
  }
  for(int i=0;i<n2;i++){
    R[i]=A[mid+i];
  }
  i=0; j=0;
  for(int k=left;k<right;k++){
    if(L[i]<=R[j]){
      A[k]=L[i];
      i++;
    }else{
      A[k]=R[j];
      j++;
    }
  }
}

void mergeSort(int A[],int left,int right){
  int mid;
  if(left+1<right){
    mid=(int)(left+right)/2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}

int main(){
  int n;
  std::cin>>n;
  int A[n];
  for(int i=0;i<n;i++){
    std::cin>>A[i];
  }
  int left=0;
  int right=n-1;
  mergeSort(A,left,right);
}

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(a[left + i])
    for j in range(n2):
        R.append(a[mid + j])
    L.append(500001)
    R.append(500001)
    i=0
    j=0
    for k in range(left, right):
        counter += 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(i) for i in a]))
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(a[left + i])
    for j in range(n2):
        R.append(a[mid + j])
    L.append(500001)
    R.append(500001)
    i=0
    j=0
    for k in range(left, right):
        counter += 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(i) for i in a]))
print(*a)
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    L = []
    R = []
    L = a[left:mid] + [500001]
    R = a[mid:right] + [500001]
    i=0
    j=0
    for k in range(left, right):
        counter += 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(i) for i in a]))
print(*a)
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [500001]
    R = a[mid:right] + [500001]
    i=0
    j=0
    for k in range(left, right):
        counter += 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(i) for i in a]))
print(*a)
print(counter)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [500001]
    R = a[mid:right] + [500001]
    i=0
    j=0
    for k in range(left, right):
        counter += 1
        if(L[i] <= R[j]):
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

Solution code:
SEN = 500001
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [SEN]
    R = a[mid:right] + [SEN]
    i=0
    j=0
    for k in range(left, right):
        counter += 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()))
mergeSort(a, 0, n)
print(*a)
print(counter)