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: Time Limit Exceeded

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

def merge(A, left, mid, right, n):
    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(100000000001)
    R.append(100000000001)
    i = j = 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n])))+'\n'+str(S[n]))

Submission status: Time Limit Exceeded

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 = [None for _ in range(n1+1)]
    r = [None for _ 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
    
    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: Time Limit Exceeded

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 = []
    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 = 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: Time Limit Exceeded

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 = []
    r = []
    for i in range(n1):
        l.append(a[left + i])
    for i in range(n2):
        r.append(a[mid + i])
    
    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: Time Limit Exceeded

Solution code:
cnt = 0

def merge(array, left, middle, right):
    n1 = middle - left
    n2 = right - middle
    L = []
    R = []
    for i in range(n1):
        L.append(array[left + i])
    for i in range(n2):
        R.append(array[middle + i])
    L.append(float("inf"))
    R.append(float("inf"))
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1


def mergeSort(array, left, right):
    if left + 1 < right:
        middle = int((left + right) / 2.)
        mergeSort(array, left, middle)
        mergeSort(array, middle, right)
        merge(array, left, middle, right)


n = int(input())
array = [int(x) for x in input().split()]
mergeSort(array, 0, len(array))
print(*array)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import array

def Merge_sort(A):

    def merge(A,left,mid,right):
        global ncmp
   
        t1=array.array('q',[])
        t2=array.array('q',[])        
        for i in range(left,mid):
            t1.append(A[i])
        for i in range(mid,right):
            t2.append(A[i])
        
        i=0
        j=0
        k=0
        maxi=mid-left
        maxj=right-mid
        while i<maxi and j<maxj:
            if t1[i]<=t2[j]:
                A[left+k]=t1[i]
                i+=1
                k+=1
            else:
                A[left+k]=t2[j]
                j+=1
                k+=1
            ncmp+=1
                
        if i==maxi and j<maxj:
            for w in range(j,maxj):
                A[left+k]=t2[w]
                k+=1
                ncmp+=1
                
   
        if j==maxj and i<maxi:
            for w in range(i,maxi):
                A[left+k]=t1[w]
                k+=1
                ncmp+=1

   

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

    mergesort(A,0,len(A))


ncmp=0
n=int(input())
arr=array.array('L')
arr.extend([int(x) for x in input().split()])
Merge_sort(arr)

length=len(arr)
for i in range(0,length-1):
    print(arr[i],end=' ')   
print(arr[length-1])
print(ncmp)

Submission status: Time Limit Exceeded

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] = 10000000000
    R[n2] = 10000000000
    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: Time Limit Exceeded

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(100000000001)
    R.append(100000000001)
    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: Time Limit Exceeded

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(1000000001)
    R.append(1000000001)
    i=0
    j=0
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        count+=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: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
    global x
    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
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 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()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)

Submission status: Time Limit Exceeded

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

    for i in range(n1):
        L[i]=A[left+i]
    for j in range(n2):
        R[j]=A[mid+j]
    L[n1]=float("inf")
    R[n2]=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: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
    global x
    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 = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 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()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)

Submission status: Time Limit Exceeded

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 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+=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: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
    global x
    n1 = mid - left
    n2 = right - mid
    l = []
    r = [] 
    for i in range(max(n1,n2)):
        if i < n1: l.append(a[left + i])
        if i < n2: r.append(a[mid + i])
    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
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 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()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)

Submission status: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
    global x
    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 = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 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()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)

Submission status: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
#    global x
    x = 0
    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 = 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
        x += 1
    return x

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

n = int(input())
s = list(map(int,input().split()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)

Submission status: Time Limit Exceeded

Solution code:
def merge(a, left, mid, right):
    x = 0
    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 = 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
        x += 1
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])

Submission status: Time Limit Exceeded

Solution code:

def merge(a, left, mid, right,x):
    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 = 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
        x[0] += 1

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

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])

Submission status: Time Limit Exceeded

Solution code:
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 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: Time Limit Exceeded

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

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=[0 for i in range(n)]
instr=input().split()
for i in range(n):
	S[i]=int(instr[i])
cnt=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]=float('inf')
	R[n2]=float('inf')
	i=0
	j=0
	for k in range(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=int((left+right)/2)
		mergeSort(A,left,mid)
		mergeSort(A,mid,right)
		merge(A,left,mid,right)

mergeSort(S,0,n)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
#    L=[0]*(n1+1)
#    R=[0]*(n2+1)
    global L, R
    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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
L=[0]*(n+1)
R=[0]*(n+1)
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
#    L=[0]*(n1+1)
#    R=[0]*(n2+1)
    global L, R
    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

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(input().split())
for i in range(n):
    S[i]=int(S[i])
L=[0]*(n//2+2)
R=[0]*(n//2+2)
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    cnt += (right-left)
    for k in range(left,right):
#        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    cnt += (right-left)
    for k in range(left,right):
#        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

# 分割した配列をソート
def merge(input: list, m: int)-> list:
    i, j = 0, m
    input_len = len(input)
    tmp_nums = []

    for k in range(0, input_len):
        if j > input_len - 1:
            tmp_nums.insert(k, input[i])
            i += 1
        elif i > m - 1:
            tmp_nums.insert(k, input[j])
            j += 1
        elif input[i] < input[j]:
            tmp_nums.insert(k, input[i])
            i += 1
        else:
            tmp_nums.insert(k, input[j])
            j += 1

    return tmp_nums

# 再帰でマージソート
def merge_sort(input: list)-> list:
    input_len = len(input)
    compare_num = input_len

    if input_len > 1:
        m = int(input_len / 2)
        out = merge_sort(input[:m])
        input[:m] = out[0]
        compare_num += out[1]

        out = merge_sort(input[m:])
        input[m:] = out[0]
        compare_num += out[1]

        input = merge(input, m)

    return input, compare_num

n = int(input())
input_list = list(map(int, input().split(' ')))

input_list = merge_sort(input_list)

print(*input_list[0])
print(input_list[1] - n)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    i, j = 0, 0
    for k in range(left,right):
        if i >= n1:
            A[k] = R[j]
            j += 1
        elif j >= n2:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        global cnt
        cnt += 1

def MergeSort(A, left, right):
    if left+1 < right:
        if (left + right) % 2 == 0:
            mid = int((left + right)/2)
        else:
            mid = int((left + right -1)/2)
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    i, j = 0, 0
    for k in range(left,right):
        if i >= n1:
            A[k] = R[j]
            j += 1
        elif j >= n2:
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        global cnt
        cnt += 1

def MergeSort(A, left, right):
    if left+1 < right:
        if (left + right) % 2 == 0:
            mid = int((left + right)/2)
        else:
            mid = int((left + right -1)/2)
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)