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:
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(10 ** 9)
    R.append(10 ** 9)
    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:
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(10 ** 9)
    R.append(10 ** 9)
    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)

mergesort(s, 0, n)

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

Submission status: Time Limit Exceeded

Solution code:
t = 0
SENTINEL = 1e+9


def sort(a, b):
    global t
    a.append(SENTINEL)
    b.append(SENTINEL)
    i, j = 0, 0
    while i < len(a)-1 or j < len(b)-1:
        t += 1
        if a[i] < b[j]:
            yield a[i]
            i += 1
        else:
            yield b[j]
            j += 1


def merge(a, left, mid, right):
    left_list, right_list = a[left:mid], a[mid:right]
    for index, value in zip(range(left, right), sort(left_list, right_list)):
        a[index] = value


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


def main():
    global t
    input()
    a = [int(i) for i in input().split()]
    merge_sort(a, 0, len(a))
    print(*a)
    print(t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
t = 0
SENTINEL = 1e+9


def sort(a, b):
    global t
    a.append(SENTINEL)
    b.append(SENTINEL)
    i, j = 0, 0
    while i < len(a)-1 or j < len(b)-1:
        t += 1
        if a[i] < b[j]:
            yield a[i]
            i += 1
        else:
            yield b[j]
            j += 1


def merge(a, left, mid, right):
    left_list, right_list = a[left:mid], a[mid:right]
    for index, value in zip(range(left, right), sort(left_list, right_list)):
        a[index] = value


def merge_sort(a, left, right):
    global t
    if right-left == 1:
        return
    elif right-left == 2:
        t += 2
        a[left], a[right-1] = min(a[left], a[right-1]), max(a[left], a[right-1])
    else:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)


def main():
    global t
    input()
    a = [int(i) for i in input().split()]
    merge_sort(a, 0, len(a))
    print(*a)
    print(t)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

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

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
for i in range(len(S)-1):
    print(S[i], end=" ")
print(S[-1])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

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

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
print(' '.join(map(str, S)))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = A[p:p+n1]
    R = A[q:q+n2]
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

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

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
print(' '.join(map(str, S)))
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
SENTINEL = 2 ** 32
cnt = 0
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] = SENTINEL
    R[n2] = SENTINEL
    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 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)

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

Submission status: Time Limit Exceeded

Solution code:
m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=list(range(0,n1+1))
    ar=list(range(0,n2+1))
    for i in range(n1):
        el[i]=a[left+i]
    for i in range(n2):
        ar[i]=a[mid+i]
    el[n1]=float("inf")
    ar[n2]=float("inf")
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[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)

a=[]
n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)

Submission status: Time Limit Exceeded

Solution code:
m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=list(range(0,n1+1))
    ar=list(range(0,n2+1))
    for i in range(n1):
        el[i]=a[left+i]
    for i in range(n2):
        ar[i]=a[mid+i]
    el[n1]=float("inf")
    ar[n2]=float("inf")
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[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)


n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)

Submission status: Time Limit Exceeded

Solution code:
m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=list(range(0,n1+1))
    ar=list(range(0,n2+1))
    for i in range(n1):
        el[i]=a[left+i]
    for i in range(n2):
        ar[i]=a[mid+i]
    el[n1]=float("inf")
    ar[n2]=float("inf")
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[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)
    else:
        if(a[left]>a[right-1]):
            a[left],a[right-1]=a[right],a[left]



n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)

Submission status: Time Limit Exceeded

Solution code:
count = 0

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

    L.append(float("inf"))
    R.append(float("inf"))

    r_id,l_id = 0,0
    for k in range(left,right):
        count += 1
        if(L[l_id] <= R[r_id]):
            A[k] = L[l_id]
            l_id += 1
        else:
            A[k] = R[r_id]
            r_id += 1

def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        margeSort(A,left,mid)
        margeSort(A,mid,right)
        marge(A,left,mid,right)


n = int(input())
s = input()
A = []
A = list(map(int,s.split()))

margeSort(A,0,n)

A_str = map(str,A)
print(" ".join(list(A_str)))
print(count)

Submission status: Time Limit Exceeded

Solution code:
count = 0
INFTY = 10 ** 10

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(INFTY)
  R.append(INFTY)

  i = 0
  j = 0
  for k in range(left, right):
    count = 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 = int((left + right)/2);
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

import sys

n = sys.stdin.readline()
for line in sys.stdin:
  items = line.strip().split()
  items = [ int(x) for x in items ]
  mergeSort(items, 0, len(items))
  print(" ".join(map(str, items)))
  print(count)

Submission status: Time Limit Exceeded

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

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

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
mergeSort(l, 0, n)

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

Submission status: Time Limit Exceeded

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

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

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
mergeSort(l, 0, n)

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

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
#1_5_B
def merge_sort(array):
    if len(array) > 1:
        L, countL = merge_sort(array[0:len(array)//2])
        R, countR = merge_sort(array[len(array)//2:])
        return merge(L, R, countL+countR)

    if len(array) == 1:
        return [array, 0]

def merge(L, R, count=0):
    L.append(10**9+1)
    R.append(10**9+1)
    response = []
    i = 0
    j = 0
    for k in range(len(L)-1 + len(R)-1):
        if L[i] <= R[j]:
            response.append(L[i])
            i += 1
            count += 1
        else:
            response.append(R[j])
            j += 1
            count += 1
    return [response, count]

n = int(input())
S = list(map(int, input().split()))
print(' '.join(map(str, merge_sort(S)[0])))
print(merge_sort(S)[1])

Submission status: Time Limit Exceeded

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


import sys


class MergeSort(object):

    def __init__(self, a):
        self.a = a
        self.compare = 0

    def merge(self, left, mid, right):
        n1 = mid - left
        n2 = right - mid
        l = self.a[left: mid]
        r = self.a[mid: right]
        l.append(sys.maxsize)
        r.append(sys.maxsize)
        (i, j) = (0, 0)
        for k in range(left, right):
            self.compare += 1
            if l[i] <= r[j]:
                self.a[k] = l[i]
                i += 1
            else:
                self.a[k] = r[j]
                j += 1

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

    def execute_merge_sort(self):
        self.merge_sort(0, len(self.a))
        return self.a


def main():
    n = int(input())
    s = [int(x) for x in input().split()]
    ms = MergeSort(s)
    print(" ".join(map(str, ms.execute_merge_sort())))
    print(ms.compare)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


import sys
import array


class MergeSort(object):

    def __init__(self, a):
        self.a = a
        self.compare = 0

    def merge(self, left, mid, right):
        n1 = mid - left
        n2 = right - mid
        l = self.a[left: mid]
        r = self.a[mid: right]
        l.append(10 ** 9 + 1)
        r.append(10 ** 9 + 1)
        (i, j) = (0, 0)
        for k in range(left, right):
            self.compare += 1
            if l[i] <= r[j]:
                self.a[k] = l[i]
                i += 1
            else:
                self.a[k] = r[j]
                j += 1

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

    def execute_merge_sort(self):
        self.merge_sort(0, len(self.a))


def main():
    n = int(sys.stdin.readline())
    s = array.array("L", (int(x) for x in sys.stdin.readline().split()))
    ms = MergeSort(s)
    ms.execute_merge_sort()
    print(" ".join(map(str, ms.a)))
    print(ms.compare)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right, counter):
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [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], R[n2] = float("inf"), float("inf")
  i, j = 0, 0
  for k in range(left, right):
    next(counter)
    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, counter):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, counter)
    mergeSort(A, mid, right, counter)
    merge(A, left, mid, right, counter)

N = int(input())
A = [int(i) for i in input().split()]
counter = count(0)
mergeSort(A, 0, len(A), counter)
print(*A)
print(next(counter))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right, counter):
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [None]*(n2+1)
  for i in range(n1):
    L[i] = int(A[left + i])
  for i in range(n2):
    R[i] = int(A[mid + i])
  L[n1], R[n2] = float("inf"), float("inf")
  i, j = 0, 0
  for k in range(left, right):
    next(counter)
    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, counter):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, counter)
    mergeSort(A, mid, right, counter)
    merge(A, left, mid, right, counter)

N = int(input())
A = input().split()
counter = count(0)
mergeSort(A, 0, len(A), counter)
print(*A)
print(next(counter))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right, counter):
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [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] = R[n2] = float("inf")
  i = j = 0
  for k in range(left, right):
    next(counter)
    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, counter):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, counter)
    mergeSort(A, mid, right, counter)
    merge(A, left, mid, right, counter)

N = int(input())
A = [int(i) for i in input().split()]
counter = count(0)
mergeSort(A, 0, len(A), counter)
print(*A)
print(next(counter))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [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] = R[n2] = float("inf")
  i = j = 0
  for k in range(left, right):
    counter += 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 = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = [None]*(n1+1), [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] = R[n2] = float("inf")
  i = 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
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def merge(a, l, m, r):
    global cnt
    n1, n2 = m - l, r - m
    ll = deque(a[l + i] for i in range(n1))
    rl = deque(a[m + i] for i in range(n2))
    for k in range(l, r):
        a[k] = (ll if not rl or ll and ll[0] <= rl[0] else rl).popleft()
        cnt += 1


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


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

Submission status: Time Limit Exceeded

Solution code:
def merge(a, l, m, r):
    global cnt
    n1, n2 = m - l, r - m
    ll = list(a[l + i] for i in range(n1))
    rl = list(a[m + i] for i in range(n2))
    ll.append(1e9 + 1)
    rl.append(1e9 + 1)
    i, j = 0, 0
    for k in range(l, r):
        if ll[i] < rl[j]:
            a[k] = ll[i]
            i += 1
        else:
            a[k] = rl[j]
            j += 1
        cnt += 1


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


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

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

Solution code:
def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    banpei = 10 ** 9 + 1
    L = [A[left + i] for i in range(n1)] + [banpei]
    R = [A[mid + i] for i in range(n2)] + [banpei]

    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 merge_Sort(A, left, right):
    if 1 < right - left:
        mid = int((left + right) / 2)
        merge_Sort(A, left, mid)
        merge_Sort(A, mid, right)
        merge(A, left, mid, right)

n = int(input())
A = list(map(int, input().split()))
count = 0
merge_Sort(A, 0, n)
print(' '.join(map(str, A)))
print(count)

Submission status: Time Limit Exceeded

Solution code:
sentinel = 10**10
count = 0
def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [0 for x in range(n1 + 1)]
    R = [0 for x in range(n2 + 1)]
    L[n1] = sentinel
    R[n2] = sentinel
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    i = 0
    j = 0
    for k in range(left, right):
        global count
        count += 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:
        mid = (left + right) // 2
        Merge_Sort(A, left, mid)
        Merge_Sort(A, mid, right)
        Merge(A, left, mid, right)


n = input()
A = list(map(int, input().split()))
Merge_Sort(A, 0, len(A))
print(*A)
print(count)

Submission status: Time Limit Exceeded

Solution code:
#coding:UTF-8
def Marge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[]
    R=[]
    c=0
    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])
    L.append(100000000000000000)
    R.append(100000000000000000)
    i=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
    return c
            
def MS(A,left,right,c):
    if left+1<right:
        mid=int((left+right)/2)
        c=MS(A,left,mid,c)
        c=MS(A,mid,right,c)
        c+=Marge(A,left,mid,right)
    return c
  
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    c=0
    count=MS(A,0,n,c)
    for i in range(n):
        A[i]=str(A[i])
    print(" ".join(A))
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
def merge(l,r):
    global count
    l_index = 0
    r_index = 0
    merge_list = []
    l.append(pow(10,9) + 1)
    r.append(pow(10,9) + 1)

    for k in range(len(l) + len(r) - 2):
        count += 1
        if l[l_index] < r[r_index]:
            merge_list.append(l[l_index])
            l_index += 1
        else:
            merge_list.append(r[r_index])
            r_index += 1

    return merge_list
    
def merge_sort(target_list):
    if len(target_list) == 1:
        return target_list
    
    mid = int(len(target_list) / 2)
    
    r = merge_sort(target_list[mid:])
    l = merge_sort(target_list[:mid])
    
    return merge(l, r)
    
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    global count
    count = 0
    print(" ".join([str(n) for n in merge_sort(target_list)]))
    print(count)

Submission status: Time Limit Exceeded

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

import sys

_input = sys.stdin.readlines()
array_length = int(_input[0])
array = list(map(int, _input[1].split()))
# print(array_length, array)
assert array_length == len(array)


def merge(A, left, mid, right):
    global count
    
    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 j in range(n2):
        R[j] = A[mid + j]

    L[n1], R[n2] = [1e9] * 2
    i, j = 0, 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

    return None


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


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Time Limit Exceeded

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

import sys

_input = sys.stdin.readlines()
array_length = int(_input[0])
array = list(map(int, _input[1].split()))
# print(array_length, array)
# assert array_length == len(array)


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

    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 j in range(n2):
        R[j] = A[mid + j]

    L[n1], R[n2] = [1e9] * 2
    i, j = 0, 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

    return None


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


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Time Limit Exceeded

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

import sys

_input = sys.stdin.readlines()
array_length = int(_input[0])
array = list(map(int, _input[1].split()))
# print(array_length, array)
# assert array_length == len(array)


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

    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1 + 1)]
    R = [0 for _ in range(n2 + 1)]

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

    for n in range(n2):
        R[n] = A[mid + n]

    # L[n1], R[n2] = [1e9] * 2
    # i, j = 0, 0
    L[n1] = 1e9
    R[n2] = 1e9
    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

    return None


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


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)