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:
cnt = 0

def merge(A, left, mid, right):
    global cnt
    L, R = A[left:mid], A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))

    i, j = 0, 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 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 main():
    global cnt
    n = int(raw_input())
    A = map(int, raw_input().split())

    cnt = 0
    merge_sort(A, 0, n);

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


main()

Submission status: Accepted

Solution code:
# coding=utf-8
def merge(a, left, mid, right):
    n1 = mid-left
    n2 = right - mid

    left_list = [a[left + i] for i in range(n1)]
    right_list = [a[mid + i] for i in range(n2)]
    left_list.append(1000000007)
    right_list.append(1000000007)

    i = 0
    j = 0
    ctr = 0
    for k in range(left, right):
        ctr += 1
        if left_list[i] <= right_list[j]:
            a[k] = left_list[i]
            i += 1
        else:
            a[k] = right_list[j]
            j += 1
    return ctr


def merge_sort(a, left, right, counter):
    if left+1 < right:
        mid = (left + right)//2
        counter1 = merge_sort(a, left, mid, counter)[1]
        counter2 = merge_sort(a, mid, right, counter)[1]
        counter += merge(a, left, mid, right)
        counter += counter1
        counter += counter2
    return a, counter


if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))
    merge_counter = 0
    S, merge_counter = merge_sort(S[:], 0, len(S), merge_counter)

    print(' '.join(map(str, S)))
    print(merge_counter)

Submission status: Accepted

Solution code:
def mergeArray(a,b,bLength,c,cLength):
    global count
    apos,bpos,cpos=(0,0,0)
    while bpos<bLength and cpos<cLength:
        if b[bpos]<=c[cpos]:
            a[apos]=b[bpos]
            bpos+=1
        else:
            a[apos]=c[cpos]
            cpos+=1
        apos+=1
        count+=1
    
    while bpos<bLength:
        a[apos]=b[bpos]
        apos+=1
        bpos+=1
        count+=1
    
    while cpos<cLength:
        a[apos]=c[cpos]
        apos+=1
        cpos+=1
        count+=1

def mergeSort(a,aLength):
    b=[]
    c=[]
    if aLength>=2:
        b=a[:aLength//2]
        c=a[aLength//2:]
        mergeSort(b,len(b))
        mergeSort(c,len(c))
    mergeArray(a,b,len(b),c,len(c))

count=0
aLength=int(input())
a=list(map(int,input().split()))
mergeSort(a,aLength)
print(*a)
print(count)

Submission status: Accepted

Solution code:
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left: left + n1] + [INF]
    R = A[mid: mid + n2] + [INF]
    i = 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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
INF = float("inf")
cnt = 0
def merge(A, left, mid, right):
    L = A[left: mid] + [INF]
    R = A[mid: right] + [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
    global cnt
    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)
n = int(input())
S = list(map(int, input().split()))
mergeSort(S, 0, n)
print(*S)
print(cnt)

Submission status: Accepted

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

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [None]*(n1+1)
    R = [None]*(n2+1)
    L[:n1] = A[left:left+n1]
    R[:n2] = A[mid:mid+n2]

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

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

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

    mergeSort(S, 0, n)

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

Submission status: Accepted

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

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

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

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

    mergeSort(S, 0, n)

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

Submission status: Accepted

Solution code:
count = 0

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

    l = a[left:mid]
    r = a[mid:right]
    l.append(10**9+1)
    r.append(10**9+1)

    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)


if __name__ == '__main__':
    n = int(input())
    a = [int(x) for x in input().split()]

    mergeSort(a, 0, n)

    print(*a)
    print(count)

Submission status: Accepted

Solution code:
INF = 10 ** 10

def merge(A, left, mid, right):
    c = 0
    n1 = mid - left
    n2 = right - mid
    Left = [A[left+i] for i in range(n1)]
    Right = [A[mid+i] for i in range(n2)]
    Left.append(INF)
    Right.append(INF)
    i=0
    j=0
    for k in range(left, right):
        c += 1
        if Left[i] <= Right[j]:
            A[k] = Left[i]
            i += 1
        else:
            A[k] = Right[j]
            j += 1
    return c

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

if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    c = mergeSort(hoge, 0, len(hoge))
    print (' '.join([str(x) for x in hoge]))
    print (c)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global c
    L=A[left:mid]+[1e10]
    R=A[mid:right]+[1e10]
    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
        c+=1
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
c=0
n=int(input())
A=list(map(int,input().split()))
mergeSort(A, 0, n)
print(*A)
print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L=A[l:m]+[1e10]
 R=A[m:r]+[1e10]
 i=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
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m)
  s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e10],A[m:r]+[1e10]
 i=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
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Submission status: Accepted

Solution code:
def g(A,l,m,r):
 global c
 L,R=A[l:m]+[1e9],A[m:r]+[1e9]
 i=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
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m);s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)
print(c)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
SENTINEL = 10**9 + 1


def merge_sort(alist):
    """Sort alist using mergesort.
    Returns a tuple of the number of comparisons and sorted list.

    >>> merge_sort([8, 5, 9, 2, 6, 3, 7, 1, 10, 4])
    (34, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    """
    def _sort(left, right):
        count = 0
        if left + 1 < right:
            mid = (left + right) // 2
            count += _sort(left, mid)
            count += _sort(mid, right)
            count += merge(left, mid, right)

        return count

    def merge(left, mid, right):
        count = 0
        ll = alist[left:mid] + [SENTINEL]
        rl = alist[mid:right] + [SENTINEL]

        i = j = 0
        for k in range(left, right):
            count += 1
            if ll[i] <= rl[j]:
                alist[k] = ll[i]
                i += 1
            else:
                alist[k] = rl[j]
                j += 1

        return count

    comp = _sort(0, len(alist))
    return (comp, alist)


def run():
    _ = int(input())  # flake8: noqa

    li = [int(i) for i in input().split()]

    (c, s) = merge_sort(li)
    print(" ".join([str(i) for i in s]))
    print(c)


if __name__ == '__main__':
    run()

Submission status: Accepted

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


def merge(a, left, mid, right):
    global count
    la = a[left:mid] + [float("inf")]
    ra = a[mid:right] + [float("inf")]

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


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

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

Submission status: Accepted

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

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [10 ** 9 + 1]
    R = A[mid:right] + [10 ** 9 + 1]
    i , j = 0, 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(" ".join(list(map(str, S[:n]))))
print(S[n])

Submission status: Accepted

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

def merge(A, left, mid, right, n):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]  + [10 ** 9 + 1]
    R = A[mid:right] + [10 ** 9 + 1]
    L.append(1000000001)
    R.append(1000000001)
    i = j = 0
    for k in range(left, right):
        A[n] += 1
        if L[i] <= R[j]:
            key = L[i]
            A[k] = key
            i += 1
        else:
            key = R[j]
            A[k] = key
            j += 1
    return A

n = int(input())
A = list(map(int, input().split()))
A.append(0)
S = mergeSort(A, 0, len(A) - 1, n)
print(' '.join(list(map(str, S[:n]))))
print(S[n])

Submission status: Accepted

Solution code:
import math
def merge(a, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1]
    r = a[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    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 = math.ceil((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()))
c = 0
mergeSort(a, 0, n)
print(" ".join(map(str, a)))
print(c)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 19:22:34 2018
ALDS-1-5-C
@author: maezawa
"""
cnt = 0
n = int(input())
a = list(map(int, input().split()))

def merge_sort(a, left, right):
    #global cnt
    #cnt += 1
    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 cnt
    n1 = mid - left
    n2 = right - mid
    
    l = a[left:mid].copy()
    r = a[mid:right].copy()
    
    l.append(10**10)
    r.append(10**10)
    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
            
merge_sort(a, 0, len(a))
print(a[0], end='')
for i in range(1,len(a)):
    print(' {}'.format(a[i]), end='')
print()
print(cnt)

Submission status: Accepted

Solution code:
count = 0

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

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 = int(input())
S = list(map(int, input().split(' ')))

merge_sort(S, 0, n)
print(' '.join(list(map(str, S))))
print(count)

Submission status: Accepted

Solution code:
cnt = 0

def merge(array, left, middle, right):
    n1 = middle - left
    n2 = right - middle
    L = array[left:left + n1] + [float("inf")]
    R = array[middle:middle + n2] + [float("inf")]
    i = 0
    j = 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1


def mergeSort(array, left, right):
    if left + 1 < right:
        middle = int((left + right) / 2.)
        mergeSort(array, left, middle)
        mergeSort(array, middle, right)
        merge(array, left, middle, right)


n = int(input())
array = [int(x) for x in input().split()]
mergeSort(array, 0, len(array))
print(*array)
print(cnt)

Submission status: Accepted

Solution code:
count=0
def merge(A, left, mid, right):
    global count
    L=A[left:mid]+[2**32]
    R=A[mid:right]+[2**32]
    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
        count+=1
def merge_sort(A, left, right):
    if left+1 < right:
        mid=(left+right)//2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right) 

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

Submission status: Accepted

Solution code:

def merge(a, left, mid, right):
    x = 0
    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
        x += 1
    return x

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

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])

Submission status: Accepted

Solution code:
global cnt
cnt = 0

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

    i = 0
    j = 0
    global cnt
    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 mergesort(A, left, right):
    rsl = []
    if left+1 < right:
        mid = int((left+right)/2)
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        rsl = merge(A, left, mid, right)

    return rsl

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

mergesort(S, 0, n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
global cnt
cnt=0

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

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

mergeSort(S,0,n)
print(*S)
print(cnt)

Submission status: Accepted

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

def merge(a,left,mid,right):
	L=a[left:mid]
	R=a[mid:right]
	L.append(INFTY)
	R.append(INFTY)
	global cnt
	i=0
	j=0
	for k in range(left,right):
		cnt+=1
		if L[i] <= R[j]:
			a[k]=L[i]
			i+=1
		else:
			a[k]=R[j]
			j+=1
			
	
n=int(input())
cnt=0
a=list(map(int,input().split()))
merge_sort(a,0,len(a))
print(*a)
print(cnt)

Submission status: Accepted

Solution code:
cnt = 0
def merge(S,left,right,mid):
    a = mid - left
    b = right - mid
    L = S[left:left+a]+[float("inf")]
    R = S[mid:mid+b]+[float("inf")]
    j = 0
    k = 0
    for i in range(left,right):
        global cnt
        cnt+=1
        if L[j] <= R[k]:
            S[i] = L[j]
            j += 1
        else:
            S[i] = R[k]
            k += 1
            
def mergeSort(S,left,right):
    if left+1<right:
        mid = (int)((left+right)/2)
        mergeSort(S,left,mid)
        mergeSort(S,mid,right)
        merge(S,left,right,mid)
        
n = int(input())
S = list(map(int, input().split()))
mergeSort(S,0,n)
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [sentinel]
    R = a[mid:right] + [sentinel]
    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
    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 = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)

Submission status: Accepted

Solution code:
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=A[left:mid]
	R=A[mid:right]

	L.append(10e10)
	R.append(10e10)
	i = 0
	j = 0
	for k in range(left , right):
		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 = (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(*A)
print(count)

Submission status: Accepted

Solution code:
import math
def merge(x, left, mid, right):
    global m
    n1 = mid - left
    n2 = right - mid
    l = x[left:left + n1]
    r = x[mid:mid + n2]
    l.append(10e10)
    r.append(10e10)
    i = 0
    j = 0
    for k in range(left, right):
        m += 1
        if l[i] < r[j]:
            x[k] = l[i]
            i += 1
        else:
            x[k] = r[j]
            j += 1
 
def mergeSort(x, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right) / 2)
        mergeSort(x, left, mid)
        mergeSort(x, mid, right)
        merge(x, left, mid, right)
 
n = int(input())
x = list(map(int,input().split()))
m = 0
mergeSort(x, 0, n)
print(" ".join(map(str, x)))
print(m)

Submission status: Accepted

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

    global cnt

    n1=mid-left
    n2=right-mid

    inf = 100000000001
    L, R = A[left:left+n1]+[inf], A[mid:mid+n2]+[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 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)


cnt=0
n=int(input())
A=[int(x) for x in input().split()]



mergeSort(A,0,n)

print(*A)
print(cnt)

Submission status: Accepted

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)

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(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    l=a[left:mid]
    r=a[mid:right]
    l.append(float("inf"))
    r.append(float("inf"))
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if(l[i] <= r[j]):
            a[k] = l[i]
            i+=1
        else:
            a[k]=r[j]
            j+=1
 
def 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(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
count = 0
 
def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [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
    count += right - left
 
def mergeSort(a, left, right):
    if left + 1 < right:
        mid = right + (left - right)//2
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)
 
mergeSort(s, 0, n)
 
print(*s)
print(count)

Submission status: Accepted

Solution code:
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1]>l:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]

def d(A):
 l=len(A);global c;c+=l
 s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A

def s():
 print(*d(list(map(int,input().split()))))
 print(c)
if'__main__'==__name__:c=-int(input());s()

Submission status: Accepted

Solution code:
INF = 10**10


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]

    lry.append(INF)
    rry.append(INF)
    i = 0
    j = 0

    for k in range(left, right):
        if lry[i] <= rry[j]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1

    return right - left


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


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