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: Wrong Answer

Solution code:
def m(L,R):
 T=[];i=j=0
 for _ in L[:-1]+R[:-1]:
  if L[i]<R[j]:T+=[L[i]];i+=1
  else:T+=[R[j]];j+=1
 return T
def d(A):s=len(A)//2;return m(d(A[:s])+[1e9],d(A[s:])+[1e9]) if len(A)>1 else A
c=0
input()
print(*d(list(map(int,input().split()))))
print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
    la, ra = [], []
    for i in range(0, n1):
        la += [a[left + i]]
    for i in range(0, n2):
        ra += [a[mid + i]]
    la += [float("inf")]
    ra += [float("inf")]
    print(la)
    print(ra)

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


def merge_sort(a, left, right):
    # それぞれの要素数が二個の配列へ分割できるまで処理を行う
    if left + 1 < right:
        mid = int((left + right) / 2)
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)

merge_sort(A, 0, N)
print(count)
print(*A)

Submission status: Wrong Answer

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
    la, ra = [], []
    for i in range(0, n1):
        la += [a[left + i]]
    for i in range(0, n2):
        ra += [a[mid + i]]
    la += [float("inf")]
    ra += [float("inf")]
    print(la)
    print(ra)

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


def merge_sort(a, left, right):
    # それぞれの要素数が二個の配列へ分割できるまで処理を行う
    if left + 1 < right:
        mid = int((left + right) / 2)
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


merge_sort(A, 0, N)
print(*A)
print(count)

Submission status: Wrong Answer

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))))
print(S[n])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""

n = int(input())
a = list(map(int, input().split()))

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

def merge(a, left, mid, right):
    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):
        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()

Submission status: Wrong Answer

Solution code:
def merge(A, left, mid, right):
    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
        else:
            A[k] = R[j]
            j = j + 1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

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

Submission status: Wrong Answer

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)
    print(A)
    print(count)

Submission status: Wrong Answer

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 in A:
        if i == A[-1]:
            print(i)
        else:
            print(i,end=" ")
    print(count)

Submission status: Wrong Answer

Solution code:
def merge_sort(A):
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left,right)
def merge(left, right):
    merged = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if i < len(left):
        merged.extend(left[i:])
    if j < len(right):
        merged.extend(right[j:])
    return merged

n=int(input())
A=[0 for i in range(n)]
A=input().split()
for i in range(n):
    A[i]=int(A[i])
left=0
right=n
A=merge_sort(A)
print(A)

Submission status: Wrong Answer

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 x in S:
	if x!=S[n-1]: print(x,end=' ')
	else: print(x)
print(cnt)

Submission status: Wrong Answer

Solution code:
cnt = 0
INFTY=10**10
def merge_sort(a,left,right):
	if left+1<right:
		mid=(left+right)//2
		merge_sort(a,left,mid)
		merge_sort(a,mid,right)
		merge(a,left,mid,right)

def merge(a,left,mid,right):
	L=a[left:mid]
	R=a[mid:right]
	L.append(INFTY)
	R.append(INFTY)
	global cnt
	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
			
	
n=int(input())
cnt=0
a=list(map(int,input().split()))
merge_sort(a,0,len(a))
print(a)
print(cnt)

Submission status: Wrong Answer

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

def mergeSort(A,left,right):
    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=input().split()
left=0
right=n
for i in range(n):
    S[i]=int(S[i])
mergeSort(S,left,right)
for i in range(n):
    print(S[i],end=" ")
print("")

Submission status: Wrong Answer

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): 
        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)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))
c = 0

mergeSort(S, 0, n)

print(S)
print(c)

Submission status: Wrong Answer

Solution code:
def merge(A, left, mid, right, c):
    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): 
        if L[i] <= R[j]:
            c = c+1
            A[k] = L[i]
            i = i + 1
        else:
            c = c+1
            A[k] = R[j]
            j = j + 1

def mergeSort(A, left, right, c):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, c)
    mergeSort(A, mid, right, c)
    merge(A, left, mid, right, c)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))
c = 0

mergeSort(S, 0, n, c)

print(S)
print(c)

Submission status: Wrong Answer

Solution code:
def merge_sort(A,cnt):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = A[:mid]
    cnt.append(1)
    right = A[mid:]
    left = merge_sort(left,cnt)
    right = merge_sort(right,cnt)
    return merge(left,right,cnt)
def merge(left, right,cnt):
    merged = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        cnt.append(1)
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if i < len(left):
        merged.extend(left[i:])
    if j < len(right):
        merged.extend(right[j:])
    return merged

n=int(input())
A=[0 for i in range(n)]
A=input().split()
cnt=[]
for i in range(n):
    A[i]=int(A[i])
left=0
right=n
A=merge_sort(A,cnt)
print(A)
print(len(cnt)+1)

Submission status: Wrong Answer

Solution code:
def merge(A,left,center,right):
	global cnt
	l=A[left:center]
	r=A[center:right]
	l.append(float("inf"))
	r.append(float("inf"))
	j=0
	k=0
	for i in range(left,right):
		cnt+=1
		if l[j]<=r[k]:
			A[i]=l[j]
			j+=1
		else:
			A[i]=r[j]
			k+=1

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

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

Submission status: Wrong Answer

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+2 < 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: Wrong Answer

Solution code:
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    x = []
    c = right - left
    lp = 0
    rp = 0
    fa = True
    fb = True
    while True:
        if fa:
            try:
                a = L[lp]
            except:
                break
            lp += 1
            fa = False
        if fb:
            try:
                b = R[rp]
            except:
                break
            rp += 1
            fb = False
        if a < b:
            x.append(a)
            fa = True
        else:
            x.append(b)
            fb =True
    if fb:
        x.extend(R[rp-1:])
    else:
        x.extend(L[lp-1:])
    S[left:right] = x
    return c

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

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(array):
    global cnt
    mid = (len(array))
    if mid > 1:
        left = merge(array[:(int)(mid/2)])
        right = merge(array[(int)(mid/2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
                cnt += 1
            else:
                array.append(right.pop(0))
                cnt += 1
        if len(left) != 0:
            cnt += len(left)
            array.extend(left)
        elif len(right) != 0:
            cnt += len(right)
            array.extend(right)
    return array

input()

l = merge(list(map(int,input().split())))
[print(l[i],end = ' ') for i in range(len(l)-1)]
print(l[-1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(array):
    global cnt
    mid = (len(array))
    if mid > 1:
        left = merge(array[:(int)(mid/2)])
        right = merge(array[(int)(mid/2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
                cnt += 1
            else:
                array.append(right.pop(0))
                cnt += 1
        if len(left) != 0:
            cnt += len(left)
            array.extend(left)
        elif len(right) != 0:
            cnt += len(right)
            array.extend(right)
    return array

input()

l = merge(list(map(int,input().split())))
for i in range(len(l)-1):
    print(l[i],end=' ')
#[print(l[i],end = ' ') for i in range(len(l)-1)]
print(l[-1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(array):
    global cnt
    mid = (len(array))
    if mid > 1:
        left = merge(array[:(int)(mid/2)])
        right = merge(array[(int)(mid/2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
                cnt += 1
            else:
                array.append(right.pop(0))
                cnt += 1
        if len(left) != 0:
            cnt += len(left)
            array.extend(left)
        elif len(right) != 0:
            cnt += len(right)
            array.extend(right)
    return array

input()

l = merge(list(map(int,input().split())))
print(*l)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            d.reverse()
        mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0:
            if len(B)==0:
                break
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans.copy(),count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0:
            if len(B)==0:
                break
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Submission status: Time Limit Exceeded

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

INFTY = 1000000001
cnt = [0]

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

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

merge_sort(0, N)
print(" ".join(map(str, A)))
print(cnt[0])

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L, R = list(range(n1 + 1)), list(range(n2 + 1))
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 10 ** 10
    R[n2] = 10 ** 10
    i = 0
    j = 0
    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 merge_sort(A, left, right):
    if left + 1 < right:  # 1 < right - left
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
    return A

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

Submission status: Time Limit Exceeded

Solution code:

SENTINEL = 2000000000
n = int(input())
MAX = 500000
A = [int(_) for _ in input().split()]
A.append(SENTINEL)
L = ['']*(n//2+2)
R = ['']*(n//2+2)
cnt = 0


def merge(A, n, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = SENTINEL
    R[n2] = SENTINEL
    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, n, left, right):
    if left+1 < right:
        mid = (left+right)//2
        mergeSort(A, n, left, mid)
        mergeSort(A, n, mid, right)
        merge(A, n, left, mid, right)


mergeSort(A, n, 0, n)
for i in range(n-1):
    print(A[i], end=" ")
print(A[n-1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

def merge(deq, left, mid, right, compare_counter):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = [deq[left + i] for i in range(n_fore)]
    l_fore.append(sys.maxsize)
    #print(left, mid, right)
    l_rear = [deq[mid + i] for i in range(n_rear)]
    l_rear.append(sys.maxsize)
    i = j = 0
    for k in range(left, right):
        compare_counter[0] += 1
        if l_fore[i] < l_rear[j]:
            deq[k] = l_fore[i]
            i += 1
        else:
            deq[k] = l_rear[j]
            j += 1

def merge_sort(deq, left, right, compare_counter):
    compare_times = 0
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(deq, left, mid, compare_counter)
        merge_sort(deq, mid, right, compare_counter)
        merge(deq, left, mid, right, compare_counter)
    return compare_times

def main():
    n = int(input())
    deq = deque()
    [deq.append(int(x)) for x in input().split()]
    compare_counter = [0]
    compare_times = merge_sort(deq, 0, n, compare_counter)
    print(" ".join(map(str, deq)))
    print(compare_counter[0])
    return


main()

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(A, left, mid, right):
  global cnt
  #print("marge ",A,left,mid,right)
  n1 = mid - left
  n2 = right - mid
  #L = [0] * (n1+1)
  #R = [0] * (n2+1)
  L = [0 for i in range(n1+1)]
  R = [0 for i in range(n2+1)]
  
  for i in range(int(n1)):
    L[i] = A[left + i]
  for i in range(int(n2)):
    R[i] = A[mid + i]
  L[n1] = 999999999
  R[n2] = 999999999
  i = 0
  j = 0
  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):
  #print("margeSort ",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)
S = map(str, S)
print(' '.join(S))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0
def merge(A, left, mid, right):
  global cnt
  #print("marge ",A,left,mid,right)
  n1 = mid - left
  n2 = right - mid
  #L = [0] * (n1+1)
  #R = [0] * (n2+1)
  L = [0] * (n1+1)
  R = [0] * (n2+1)
  
  for i in range(int(n1)):
    L[i] = A[left + i]
  for i in range(int(n2)):
    R[i] = A[mid + i]
  L[n1] = 999999999
  R[n2] = 999999999
  i = 0
  j = 0
  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):
  #print("margeSort ",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)
S = map(str, S)
print(' '.join(S))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
s = list(map(int, input().split()))

c = 0
a = 'a'

def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

ans = mergesort(s, 0, n)

for i in ans:
    a = str(a) + str(i) + ' '
print(a[1:-1])
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'

def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

ans = mergesort(s, 0, n)

for i in ans:
    a = str(a) + str(i) + ' '
print(a[1:-1])
print(c)