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

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

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

Submission status: Time Limit Exceeded

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] = -1
    R[n2] = -1
    i = 0
    j = 0
    #global cnt
    cnt = 0

    for k in range(left, right):
        if (L[i] <= R[j] and L[i] != -1) or R[j] == -1:
            A[k] = L[i]
            i = i+1
            cnt +=1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

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

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

Submission status: Time Limit Exceeded

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

import sys
import os
import math


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

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

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

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


def merge_sort(A, left, right):
    if left + 1 == right:
        # ???????????????
        return
    else:
        # ??????????????????
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

merge_sort(A, 0, len(A))
print(*A)
print(cnt)

Submission status: Time Limit Exceeded

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] = -1
    R[n2] = -1
    i = 0
    j = 0
    global cnt
    cnt = 0

    for k in range(left, right):
        if (L[i] <= R[j] and L[i] != -1) or R[j] == -1:
            A[k] = L[i]
            i = i+1
            cnt +=1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

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

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

Submission status: Time Limit Exceeded

Solution code:
def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    global cnt
    cnt = 0

    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
            cnt +=1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

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

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

Submission status: Time Limit Exceeded

Solution code:
def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

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

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

Submission status: Time Limit Exceeded

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B
# awesome answer: 

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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


def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])

    L.append(float("inf"))
    R.append(float("inf"))
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    count += right - left


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

mergeSort(A,0,N)


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python

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

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

    i = 0
    j = 0
    k = 0
    both_flag = True

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

N = int(input())
S = list(map(int, input().split(" ")))
#S = [random.randint(0,1000000) for _ in range(500000)]
num = [0]
mergesort(S, num)
print(" ".join(map(str, S)))
print(num[0])

Submission status: Time Limit Exceeded

Solution code:
def merge(S, left, mid, right, cnt):
	S1 = S[:left]
	S2 = S[left:mid][::-1]
	S3 = S[mid:right][::-1]
	S4 = S[right:]
	while S2 and S3:
		cnt += 1
		S1.append(min(S2,S3,key = lambda X:X[-1]).pop())
	S = S1 + S2[::-1] + S3[::-1] + S4
	cnt += (len(S2)+len(S3))
	return S,cnt

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

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

Submission status: Time Limit Exceeded

Solution code:
def merge(S, left, mid, right):
	global cnt
	S1 = S[:left]
	S2 = S[left:mid][::-1]
	S3 = S[mid:right][::-1]
	S4 = S[right:]
	temp = []
	while S2 and S3:
		cnt += 1
		temp.append(min(S2,S3,key = lambda X:X[-1]).pop())
	temp += S2[::-1] + S3[::-1]
	cnt += (len(S2)+len(S3))
	S[left:right] = temp


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


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
?????????????????????Merge Sort??????????????±??????????????\??????????????¢?????´???????????§???
?¬?????????????????£????????????¨?????§????????????

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

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

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

MAX = 1000000001

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

    for i in range(n2):
        R.append(A[mid + i])

    L.append(MAX)
    R.append(MAX)
#    print("l:{} m:{} r:{} cnt:{} n1:{} n2:{}".format(left,mid,right,cnt,n1,n2))
#    print("left:{} right:{}".format(L,R))
    i = 0
    j = 0
    for k in range(left, right):
#        print("k:{} i:{} j:{}".format(k,i,j))
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
        cnt += 1
    return cnt

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
comp = 0
def merge(A, left, right):
    global comp
    if not left +1 < right:
        return [A[left]]
    mid = (left + right) // 2
    L = merge(A, left, mid)
    R = merge(A, mid, right)
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        comp += 1
        if L[i] <= R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    while i < len(L):
        comp += 1
        result.append(L[i])
        i += 1
    while j < len(R):
        comp += 1
        result.append(R[j])
        j += 1
    return result
n = int(input())
*A, = map(int, input().split())
B = merge(A, 0, n)
print(*B)
print(comp)

Submission status: Time Limit Exceeded

Solution code:
comp = 0
def merge(A, left, right):
    global comp
    if not left+1 < right:
        return [A[left]]
    if left+2 == right:
        comp += 2
        a, b = A[left:right]
        return (a, b) if a < b else (b, a)
    mid = (left + right) // 2
    L = merge(A, left, mid)
    R = merge(A, mid, right)
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        comp += 1
        if L[i] <= R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    if i < len(L):
        result.extend(L[i:])
        comp += len(L) - i
    if j < len(R):
        result.extend(R[j:])
        comp += len(R) - j
    return result

n, *A = map(int, open(0).read().split())
B = merge(A, 0, n)
print(*B)
print(comp)

Submission status: Time Limit Exceeded

Solution code:
comp = 0
def m(L, R):
    global comp
    i = j = 0
    while i < len(L) and j < len(R):
        comp += 1
        if L[i] <= R[j]:
            yield L[i]
            i += 1
        else:
            yield R[j]
            j += 1
    comp += len(L) - i + len(R) - j
    while i < len(L):
        yield L[i]
        i += 1
    while j < len(R):
        yield R[j]
        j += 1
def merge(A):
    global comp
    if len(A) == 1:
        return A
    if len(A) == 2:
        comp += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A) // 2
    L = merge(A[:mid])
    R = merge(A[mid:])
    A[:] = m(L, R)
    return A

n, *A = map(int, open(0).read().split())
B = merge(A)
print(*B)
print(comp)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = list(map(int, input().split()))
c = 0
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)]
    L.append(float('inf'))
    R.append(float('inf'))
    i,j = 0, 0
    global c
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
            c += 1
        else:
            A[k] = R[j]
            j += 1
            c += 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(S, 0, n)
print(' '.join(map(str, S)))
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = list(map(int, input().split()))
c = 0
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)] + [float('inf')]
    R = [A[mid + i] for i in range(n2)] + [float('inf')]
    i,j = 0, 0
    global c
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    c += right - left

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

mergeSort(S, 0, n)
print(' '.join(map(str, S)))
print(c)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

def merge(A, l, m, r):
    n1, n2 = m - l, r - m
    L = [A[l + i] for i in range(n1)]
    R = [A[m + i] for i in range(n2)]
    L.append(10 ** 10)
    R.append(10 ** 10)
    i, j = 0, 0
    global cnt
    for k in range(l, r):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
def merge(A, l, m, r):
    n1, n2 = m - l, r - m
    L = [A[l + i] for i in range(n1)] + [10 ** 10]
    R = [A[m + i] for i in range(n2)] + [10 ** 10]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    global cnt
    cnt += r - l

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

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

Submission status: Time Limit Exceeded

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

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


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

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


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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import os


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

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

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

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

    s_i = 0
    t_i = 0

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

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

Submission status: Time Limit Exceeded

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


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    cnt = 0
    for k in range(left, right):
        cnt += 1
        if L or R:
            if not L:
                lst[k] = R.pop(0)
            elif not R:
                lst[k] = L.pop(0)
            elif L[0] <= R[0]:
                lst[k] = L.pop(0)
            else:
                lst[k] = R.pop(0)
    return cnt


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


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

Submission status: Time Limit Exceeded

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


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


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


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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

sys.setrecursionlimit(10000)

COUNT = 0


def merge(A, left, mid, right):
    global COUNT
    L = []
    R = []

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

    L.append(math.inf)
    R.append(math.inf)

    i = 0
    j = 0

    for k in range(left, right):
        COUNT += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


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


n = int(input())
li = [int(x) for x in input().split(' ')]
mergeSort(li, 0, len(li))
print(*li)
print(COUNT)

Submission status: Time Limit Exceeded

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

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

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

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

    mergeSort(S, 0, n)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

def Merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(None)
    R.append(None)
    item_L = L.pop(0)
    item_R = R.pop(0)

    global cmp_count
    for i in range(left, right):
        cmp_count += 1
        if item_L == None:
            A[i] = item_R
            item_R = R.pop(0)
        elif item_R == None:
            A[i] = item_L
            item_L = L.pop(0)
        elif item_L <= item_R:
            A[i] = item_L
            item_L = L.pop(0)
        else:
            A[i] = item_R
            item_R = R.pop(0)

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)


import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

cmp_count = 0
Merge_Sort(A, 0, len(A))
print(' '.join(map(str,A)))
print(cmp_count)

Submission status: Time Limit Exceeded

Solution code:
import sys

def conquer(left,right,List):
    l = r = 0
    result = []
    while l < len(left) and r < len(right):
        List.append(1)
        if left[l] > right[r]:
            result.append(right[r])
            r += 1
        else:
            result.append(left[l])
            l += 1
    while l < len(left):
        List.append(1)
        result.append(left[l])
        l += 1
    while r < len(right):
        List.append(1)
        result.append(right[r])
        r += 1
    return result

def divide(data,List):
    if len(data) <= 1:
        return data
    return conquer(divide(data[0:int((0 + len(data)) / 2)],List),divide(data[int((0 + len(data)) / 2):],List),List)

def mergesort(data):
    temp = []
    result = divide(data,temp)
    for i in range(0,len(result)):
        print(result[i],end=' ' if i < len(result) - 1 else '\n')
    print(sum(temp))

for i in sys.stdin:
    temp = i.split()
    if len(temp) > 1:
        break
for i in range(0,len(temp)):
    temp[i] = int(temp[i])
mergesort(temp)

Submission status: Time Limit Exceeded

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

    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: 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(1000000001)
    R.append(1000000001)
    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)
for i in range(n - 1):
    print(S[i], end = ' ')
print(S[n - 1])
print(S[n])

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(1000000001)
    R.append(1000000001)
    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)
for i in range(n - 1):
    print(S[i], end = ' ')
print(S[n - 1])
print(S[n])

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