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:
def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    #lcount = 0
    #rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
            #lcount += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        #lcount += len(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        #rcount += len(right[rpos:])
    
    #print merged
    #return merged, lcount + rcount
    return merged, len(merged)

if __name__ == '__main__':
    n = int(raw_input())
    A = map(long, raw_input().split())
    
    sorted, count = merge_sort(A)
    print ' '.join(str(x) for x in sorted)
    print count

Submission status: Accepted

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

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

import sys

def merge(A, 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] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = R[n2] = sys.maxint
    i = 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(raw_input())
S = map(int, raw_input().split())
count = 0
mergeSort(S, 0, n)
print " ".join(map(str, S))
print count

Submission status: Accepted

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

	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
	cnt += 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)

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

Submission status: Accepted

Solution code:
cnt = 0
def merge(L,R):
    global cnt
    A = []
    i = j = 0
    n = len(L)+len(R)
    L.append(float("inf"))
    R.append(float("inf"))
    for _ in range(n):
        cnt += 1
        if L[i] <= R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 
    

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

Submission status: Accepted

Solution code:
cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    cnt += n
    A = []
    i = j = 0
    L.append(float("inf"))
    R.append(float("inf"))
    for _ in range(n):
        if L[i] <= R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 
    

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

Submission status: Accepted

Solution code:
cnt = 0
def merge(L,R):
    global cnt
    n = len(L)+len(R)
    cnt += n
    A = []
    i = j = 0
    L.append(-1)
    R.append(-1)
    for _ in range(n):
        if L[i] >= R[j]:
            A.append(L[i])
            i += 1
        else:
            A.append(R[j])
            j += 1
    return A

def mergeSort(A):
    if len(A)==1: return A
    m = len(A)//2
    return merge(mergeSort(A[:m]),mergeSort(A[m:])) 
    

if __name__=='__main__':
    n=int(input()) 
    A=list(map(int,input().split()))
    print(*mergeSort(A)[::-1])
    print(cnt)

Submission status: Accepted

Solution code:
def merge(a, left, mid, right):
    global cnt
    l = a[left:mid] + [10**9 + 1]
    r = a[mid:right] + [10**9 + 1]

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


n = int(input())
S = list(map(int, input().split()))
cnt = 0
mergesort(S, 0, n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
def merge_sort(a):
    return _merge_sort(a)

def _merge_sort(a):
    if len(a) == 1:
        return a,0
    m = len(a)/2
    b,count1 = _merge_sort(a[0:m])
    c,count2 = _merge_sort(a[m:len(a)])
    ret,count3 = merge(b,c)
    return (ret,count1+count2+count3)

def merge(b,c):
    a = []
    i = 0
    j = 0
    count = 0
    while i < len(b) and j < len(c):
        count += 1
        if b[i] > c[j]:
            a.append(c[j])
            j += 1
        else:
            a.append(b[i])
            i += 1
    if i == len(b):
        while j < len(c):
            count += 1
            a.append(c[j])
            j += 1
    elif j == len(c):
        while i < len(b):
            count += 1
            a.append(b[i])
            i += 1
    return a,count

n = int(raw_input())
a = map(int,raw_input().split(' '))
ret,count = merge_sort(a)
print ' '.join(map(str,ret))
print count

Submission status: Accepted

Solution code:
def merge(targ,first,mid,last):
    left = targ[first:mid] + [10 ** 9 + 1]
    right = targ[mid:last] + [10 ** 9 + 1]

    leftcnt = rightcnt = 0
    global ans
    for i in range(first,last):
        ans += 1
        #print(left,right,left[leftcnt],right[rightcnt],targ,ans)
        if left[leftcnt] <= right[rightcnt]:
            targ[i] = left[leftcnt]
            leftcnt += 1
        else:
            targ[i] = right[rightcnt]
            rightcnt += 1

def mergesort(targ,first,last):

    if first +1 >= last:
        pass
    else:
        mid = (first + last) // 2
        mergesort(targ,first,mid)
        mergesort(targ,mid,last)
        merge(targ,first,mid,last)


ans = 0
num = int(input())
targ = [int(n) for n in input().split(' ')]
mergesort(targ,0,num)
print(" ".join([str(n) for n in targ]))
print(ans)

Submission status: Accepted

Solution code:
import sys
n = int(input())
SENTINEL = 10000000000
COMPAR = 0

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

def merge(A, left, mid, right):
    global COMPAR
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)

    j = 0
    i = 0
    for k in range(left, right):
        COMPAR += 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)

merge_sort(A, 0, n)
print(' '.join(map(str, A)))
print(COMPAR)

Submission status: Accepted

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

import sys


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

    L = A[left:mid] + [1e9]
    R = A[mid:right] + [1e9]

    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)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert array_length == len(array)
    count = 0
    merge_sort(A=array, left=0, right=array_length)
    print(*array)
    print(count)

Submission status: Accepted

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

import sys


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

    L = A[left:mid] + [1e9]
    R = A[mid:right] + [1e9]

    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
    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__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert array_length == len(array)
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Accepted

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

import sys


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

    L = A[left:mid] + [1e9]
    R = A[mid:right] + [1e9]

    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__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert array_length == len(array)
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
def merge(target_list, left_index, right_index):
    global count
    mid_index = (left_index + right_index) // 2
    l = target_list[left_index:mid_index] + [pow(10,9) + 1]
    r = target_list[mid_index:right_index] + [pow(10,9) + 1]
    l_target = 0
    r_target = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1
    #print(target_list)
def merge_sort(target_list, left_index, right_index):
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        merge_sort(target_list, left_index, mid_index)
        merge_sort(target_list, mid_index, right_index)
        merge(target_list, left_index, right_index)
    
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    global count
    count = 0
    merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
def merge(target_list, left_index, mid_index,right_index):
    global count
    l = target_list[left_index:mid_index] + [pow(10,9) + 1]
    r = target_list[mid_index:right_index] + [pow(10,9) + 1]
    l_target = 0
    r_target = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        merge_sort(target_list, left_index, mid_index)
        merge_sort(target_list, mid_index, right_index)
        merge(target_list, left_index, mid_index,right_index)
    
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    global count
    count = 0
    merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
def merge(target_list, left_index, mid_index,right_index):
    l = target_list[left_index:mid_index] + [pow(10,9) + 1]
    r = target_list[mid_index:right_index] + [pow(10,9) + 1]
    l_target = 0
    r_target = 0
    count = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return count
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = 0
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
def merge(target_list, left_index, mid_index,right_index):
    sentinel = pow(10,9) + 1
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target = 0
    r_target = 0
    count = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return count
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
        
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
sentinel = pow(10,9) + 1
def merge(target_list, left_index, mid_index,right_index):
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target = 0
    r_target = 0
    count = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return count
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
        
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
sentinel = pow(10,9) + 1
def merge(target_list, left_index, mid_index,right_index):
    global count
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target = 0
    r_target = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        merge_sort(target_list, left_index, mid_index)
        merge_sort(target_list, mid_index, right_index)
        merge(target_list, left_index, mid_index,right_index)
        
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    global cnt
    count = 0
    merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
sentinel = pow(10,9) + 1
def merge(target_list, left_index, mid_index,right_index):
    
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target = 0
    r_target = 0
    count = 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return count
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
        
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
sentinel = pow(10,9) + 1
def merge(target_list, left_index, mid_index,right_index):
    
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target, r_target, count = 0, 0, 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        count += 1
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return count
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
        
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=jp
sentinel = pow(10,9) + 1
def merge(target_list, left_index, mid_index,right_index):
    
    l = target_list[left_index:mid_index] + [sentinel]
    r = target_list[mid_index:right_index] + [sentinel]
    l_target, r_target, count = 0, 0, 0
    #print(left_index, right_index, mid_index, l,r)
    for k in range(left_index, right_index):
        if l[l_target] < r[r_target]:
            target_list[k] = l[l_target]
            l_target += 1
        else:
            target_list[k] = r[r_target]
            r_target += 1

    return l_target + r_target
    #print(target_list)
            
def merge_sort(target_list, left_index, right_index):
    count = 0
    if left_index + 1 < right_index:
        mid_index = (left_index + right_index) // 2

        count += merge_sort(target_list, left_index, mid_index)
        count += merge_sort(target_list, mid_index, right_index)
        count += merge(target_list, left_index, mid_index,right_index)
        
    return count
if __name__ == "__main__":
    l = input()
    target_list = [int(a) for a in input().split()]
    count = merge_sort(target_list, 0, len(target_list))
    print(" ".join([str(n) for n in target_list]))
    print(count)

Submission status: Accepted

Solution code:
counter = 0

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    #print(L)
    #print(R)
    L.append(float('inf'))
    R.append(float('inf'))
    i=j=0
    global counter
    for k in range(left,right):
        counter = 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())
l = list(map(int,input().split()))
mergeSort(l,0,n)
print(*l)
print(counter)

Submission status: Accepted

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


def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


from array import array
def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)

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

from ctypes import *
class DATA(Structure):
    _fields_ = ("d", c_int * 250002),
L = DATA()
R = DATA()

def merge_with_ctypes(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L.d[i] = A[left+i]
    for i in range(n2):
        R.d[i] = A[mid+i]
    L.d[n1] = 1000000001
    R.d[n2] = 1000000001

    i = 0  # L[]??¨?????????????????????
    j = 0  # R[]??¨?????????????????????
    for k in range(left, right):
        Comp_count += 1
        if L.d[i] <= R.d[j]:
            A[k] = L.d[i]
            i += 1
        else:
            A[k] = R.d[j]
            j += 1



Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = [int(x) for x in input().split(' ')]
    #with open('ALDS1_5_B_in10.txt') as f:
    #    for line in f:
    #        if ' ' not in line:
    #            num_of_data = int(line)
    #        else:
    #            S = [int(x) for x in line.split(' ')]
    #S = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]

    # ????????????????????????
    merge_sort(S, 0, num_of_data)

    # ???????????????
    print('{0}'.format(' '.join(map(str, S))))
    print(Comp_count)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
# AIZU ONLINE JUDGE
# Introduction to Algorithms and Data Structures
# ALDS1_5_B
# Recursion / Divide and Conquer - Merge Sort

# ?????????????????????????????±??????????????\??????????????¢?????´????????????
# ????????±??????(Divide and Conquer method)?????????????????§????§£?±???§???????????§????????????????°????????????????????????????????????¨???????§£?±????????????¨??§?????????????????????????????¨???????§£?±?????????¨?????????????§£?±???????????????¨???
# ?????????????????´??????????????????????????????????????????????????°????????´???????????????????????????????????????????????¨????????£?????´?????????

# Input
# A     : ??´??????????????????
# left  : ??????????????????????????????????????????????????????
# mid   : right??¨mid???????????????????¬?????????§???????????????
# right : ??????????????????????????????????????????????????????

cnt = 0
def marge(A, left, mid, right):
    global cnt
    # ??????????????????????????????????????????
    n1 = mid-left
    n2 = right-mid

    # L[0..n1],R[0..n2]?????????
    l = []
    r = []
    for i in xrange(n1):
        l.append(A[left+i])
    for i in xrange(n2):
        r.append(A[mid+i])
    l.append(float('inf'))
    r.append(float('inf'))
    i = 0
    j = 0
    for k in xrange(left,right):
        cnt += 1
        if l[i]<=r[j]:
            A[k] = l[i]
            i+=1
        else:
            A[k] = r[j]
            j+=1

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

def main():
    n = input()
    A = map(int,raw_input().split())
    marge_sort(A,0,len(A))
    print " ".join(map(str,A))
    print cnt

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid] + [float("inf")]
    R = A[mid:right] + [float("inf")]

    i = 0
    j = 0

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

    return right - left

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 = int(input())
S = [int(s) for s in input().split()]

ans = mergeSort(S, 0, n)

print(*S)
print(ans)

Submission status: Accepted

Solution code:
import math
n = int(input())
S = list(map(int,input().split()))
M = 10**9 + 1
def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = A[left:left + n1]
    R = A[mid:mid + n2]
    L.append(M)
    R.append(M)
    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)

count = 0
mergeSort(S,0,len(S))
print(*S)
print(count)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int,input().split()))
M = 10**9 + 1
def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = A[left:left + n1]
    R = A[mid:mid + n2]
    L.append(M)
    R.append(M)
    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)

count = 0
mergeSort(S,0,len(S))
print(*S)
print(count)

Submission status: Accepted

Solution code:
def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]

  i = 0
  j = 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 count
  count += r - l

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)

SENTINEL = float('inf')
n = int(input())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(count)