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: Accepted

Solution code:
import sys
count = 0

def merge_sort(arr):
	merge_sort_(arr, 0, len(arr))

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

def merge(arr, left, mid, right):
	global count
	
	n1 = mid - left
	n2 = right - mid
	
#	L = [0] * (n1 + 1)
#	R = [0] * (n2 + 1)
#	for i in range(n1):
#		L[i] = arr[left + i]
#	for i in range(n2):3
#		R[i] = arr[mid + i]
#	L[n1] = R[n2] = sys.maxsize
	
	L = arr[left:left + n1]
	R = arr[mid:mid + n2]
	L.append(sys.maxsize)
	R.append(sys.maxsize)

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

n = int(input())
arr = list(map(int, input().split()))
merge_sort(arr)
print(" ".join(map(str, arr)))
#for i in range(n):
#	print(arr[i], end="")
#	if i != n - 1:
#		print(" ", end="")
#print()
print(count)

Submission status: Accepted

Solution code:
# Recursion / Divide and Conquer - Merge Sort
def merge(A,left,mid,right):
    global c
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid] + [10**9+1]
    R = A[mid:right] + [10**9+1]
    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
    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)
        return A

n = int(input())
S = list(map(int, input().split()))
c=0
mergeSort(S,0,n)
print(*S)
print(c)
c=0

Submission status: Runtime Error

Solution code:
cnt = 0
def merge(l, left, mid, right):
    L = l[left:mid] + [1000000]
    R = l[mid:right] + [1000000]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

Solution code:
cnt = 0
def merge(l, left, mid, right):
    L = l[left:mid] + [10000]
    R = l[mid:right] + [10000]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

Solution code:
cnt = 0
def merge(l, left, mid, right):
    L = l[left:mid] + [2**10]
    R = l[mid:right] + [2**10]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

Solution code:
EXTRA 10000
cnt = 0
def merge(l, left, mid, right):
    L = l[left:mid] + [EXTRA]
    R = l[mid:right] + [EXTRA]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

Solution code:
EXTRA = 10000
cnt = 0
def merge(l, left, mid, right):
    L = l[left:mid] + [EXTRA]
    R = l[mid:right] + [EXTRA]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            l[k] = L[i]
            i += 1
        else:
            l[k] = R[j]
            j += 1

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

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

Submission status: Runtime Error

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)
        print("left:{}, mid:{}, right:{}".format(left, mid, right))
        merge(left, mid, right)
        print(A)

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

Submission status: Runtime Error

Solution code:
import sys

compare_counter = 0
array = [0 for x in range(500000)]

def merge(left, mid, right):
    n_fore = mid - left
    n_rear = right - mid
    l_fore = array[left:left + n_fore]
    l_fore.append(sys.maxsize)
    l_rear = array[mid:mid + n_rear]
    l_rear.append(sys.maxsize)

    i = j = 0
    global compare_counter
    compare_counter += (right - left)
    for k in range(left, right):
        if l_fore[i] < l_rear[j]:
            array[k] = l_fore[i]
            i += 1
        else:
            array[k] = l_rear[j]
            j += 1


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


def main():
    start = time.time()
    n = int(input())
    for idx, tmp in enumerate(input().split()):
        array[idx] = int(tmp)

    merge_sort(0, n)

    print(" ".join(map(str, array[:n])))
    print(compare_counter)

    return


main()

Submission status: Runtime Error

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,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: Runtime Error

Solution code:
count = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    # print('merge for', left, 'to', right)
    L.append(1000000)
    R.append(1000000)
    
    # print('n1', n1)
    # print('n2', n2)
    # print('L', L)
    # print('R', R)

    i = 0
    j = 0
    C = []
    global count
    
    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
    # print(A)


def merge_sort(A, left, right):

    # print(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())
A = list(map(int, input().split()))

merge_sort(A, 0, len(A))

# print('==========')

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000)
    R.append(1000000)

    i = 0
    j = 0
    global count
    
    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 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())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    global count
    
    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 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())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
# def merge(A, left, mid, right):
#     L = A[left:mid] + [1000000]
#     R = A[mid:right] + [1000000]
#     # L.append(1000000)
#     # R.append(1000000)

#     i = 0
#     j = 0
#     global count
    
#     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 merge(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [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

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())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    global count
    
    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 merge(A, left, mid, right):
#     global count
#     inf = 10 ** 9
#     L = A[left:mid] + [inf]
#     R = A[mid:right] + [inf]
 
#     i = 0
#     j = 0
#     for k in range(left, right):
#         count += 1
#         # print(L)
#         # print(R)
#         if L[i] <= R[j]:
#             A[k] = L[i]
#             i += 1
#         else:
#             A[k] = R[j]
#             j += 1

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

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

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge_jibun(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    global count
    
    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 merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)

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

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge_jibun(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    i = 0
    j = 0
    global count
    
    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 merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)
        # merge_hoka(A, left, mid, right)

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

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge_jibun(A, left, mid, right):
    global count
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [1000000]
    # L.append(1000000)
    # R.append(1000000)

    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 merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)
        # merge_hoka(A, left, mid, right)

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

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge_jibun(A, left, mid, right):
    global count
    # inf = 10 ** 9
    L = A[left:mid] + [10 ** 4]
    R = A[mid:right] + [10 ** 4]
    # L.append(1000000)
    # R.append(1000000)

    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 merge_hoka(A, left, mid, right):
    global count
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [inf]
 
    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        # print(L)
        # print(R)
        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_jibun(A, left, mid, right)
        # merge_hoka(A, left, mid, right)

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

print(' '.join(list(map(str, A))))
print(count)

Submission status: Runtime Error

Solution code:
def merge( tS, left, mid, right ):
	global cnt
	n1 = mid - left;
	n2 = right - mid;
	tL = tS[ left : mid ];
	tR = tS[ mid : right ];	
	tL.append( 1000000001 )
	tR.append( 1000000001 )
	i = j = 0
	for k in range( left, right ):
		cnt += 1
		if tL[i] <= tR[j]:
			tS[k] = tL[i]
			i += 1
		else:
			tS[k] = tR[j]
			j += 1


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

n = int( input() )
arrS = [ int( val ) for val in input().split( ' ' ) ]
cnt = 0
mergeSort( arrS, 0, n )
print( " ".join( map( str, arrS ) ) )
print( cnt )

Submission status: Runtime Error

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]=20*10000
    ar[n2]=20*10000
    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: Runtime Error

Solution code:
m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=range(0,n1+1)
    ar=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: Runtime Error

Solution code:
INFTY = 10 ** 10

def merge(A, left, mid, right):
  global count
  n1 = mid - left;
  n2 = right - mid;

  L = []
  R = []

  L = A[left:left+n1]
  R = A[mid:mid+n2]

  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: Runtime Error

Solution code:
count = 0

def marge(A,left,mid,right):
    global count
    n1 = mid -left
    n2 = right -mid
    L = []
    R = []
    j=0
    for i in range(left,n1+left):
        L[j]=A[i]
        j += 1
    L[j+1] = float("inf")
    j=0
    for i in range(mid,n2+mid):
        R[j]=A[i]
        j += 1
    R[j+1] = float("inf")



'''
    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: Runtime Error

Solution code:
N = int(raw_input())
count = 0

A_str = raw_input().split()
A = map(int, A_str)

def merge(left, right):
    global count
    sorted_list = []
    l_index = 0
    r_index = 0

    while l_index < len(left) and r_index < len(right):
        count += 1
        if left[l_index] <= right[r_index]:
            sorted_list.append(left[l_index])
            l_index += 1
        else:
            sorted_list.append(right[r_index])
            r_index += 1

    if len(left) != l_index:
        sorted_list.extend(left[l_index:])
        count += len(left[l_index:])
    if len(right) != r_index:
        sorted_list.extend(right[r_index:])
        count += len(right[r_index:])

    return sorted_list 

def mergeSort(A):
    
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

print ' '.join(map(str, mergeSort(A)))print count

Submission status: Runtime Error

Solution code:
N = int(raw_input())
count = 0

A_str = raw_input().split()
A = map(int, A_str)

def merge(left, right):
    global count
    sorted_list = []
    l_index = 0
    r_index = 0

    while l_index < len(left) and r_index < len(right):
        count += 1
        if left[l_index] <= right[r_index]:
            sorted_list.append(left[l_index])
            l_index += 1
        else:
            sorted_list.append(right[r_index])
            r_index += 1

    if len(left) != l_index:
        sorted_list.extend(left[l_index:])
        count += len(left[l_index:])
    if len(right) != r_index:
        sorted_list.extend(right[r_index:])
        count += len(right[r_index:])

    return sorted_list 

def mergeSort(A):
    
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

print ' '.join(map(str, mergeSort(A)))print count
print count

Submission status: Runtime Error

Solution code:
global count
acount = 0


def merge(num_list, left, mid, right):
    a = mid - left
    b = right - mid
    L = []
    R = []

    for i in range(a):
        L.append(num_list[left + i])
    for i in range(b):
        R.append(num_list[mid + i])

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

    i = 0
    j = 0
    global count

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


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)

    return num_list


if __name__ == "__main__":
    num = raw_input()
    line = raw_input()

    num_list = line.strip().split()
    num_list = map(int, num_list)

    merge_list = mergeSort(num_list, 0, len(num_list))
    merge_list = map(str, merge_list)
    print " ".join(merge_list)
    print count

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    R.append[1000000001]
    L.append[1000000001]

    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
    count += right - left


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())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, N)
print(*A)
print(count)











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


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())
A = list(map(int, input().split()))
count = 0
def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    R.append[1000000001]
    L.append[1000000001]
    
    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
    count += right - left

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())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, N)
print(*A)
print(count)

Submission status: Runtime Error

Solution code:
count = 0

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)

def merge(A, left, mid, right):
    n1 = mid -left
    n2 = right - mid
    L = [0] * (n1+1)
    R = [0] * (n2+1)
    for i in range(0, n1):
        L[i] = A[left+i]
    for i in range(0, n2):
        R[i] = A[mid+i]

    L[n1] = 999999999999999999999
    R[n2] = 999999999999999999999

    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

n = int(raw_input(''))
A = raw_input('').split(' ')
mergeSort(A,0,n-1)
print A.join(' ')
print count

Submission status: Runtime Error

Solution code:
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(500001)
    R.append(500001)
    i, j, c = 0, 0, 0
    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
    return c


def merge_Sort(A, left, right):
    count = 0
    if left  + 1 < right:
        mid = int((left + right) / 2)
        count += merge_Sort(A, left, mid)
        count += merge_Sort(A, mid, right)
        count += merge(A, left, mid, right)
    return count

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

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    banpei = 10 ** 9 + 1
    L, R = L + [banpei], R + [banpei]
    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 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: Runtime Error

Solution code:
sentinel = 10**10

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):
        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):
    global count
    count += 1
    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: Runtime Error

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
count = 0
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
    print(" ".join([str(n) for n in merge_sort(target_list)]))
    print(count)

Submission status: Runtime Error

Solution code:
h, w = [int(n) for n in input().split()]

for i in range(0, h):
  for j in range(0, w):
    print("#", end='')
  print()