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] <= R[j]
      then A[k] = L[i]
           i = i + 1
      else A[k] = R[j]
           j = j + 1

Merge-Sort(A, left, right){
  if left+1 < right
    then mid = (left + right)/2;
         call Merge-Sort(A, left, mid)
         call Merge-Sort(A, mid, right)
         call Merge(A, left, mid, right) Input In the first line 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 ≤ 10 9  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

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


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


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


mergeSort(A, 0, n)
print(" ".join(list(map(str, A))))
print(count)

Solution (Python):

from collections import deque

def merge(A,B):
    ans = [0]*(len(A)+len(B))
    count=i=j=0
    A+=[10**9+1]
    B+=[10**9+1]
    for k in range(len(ans)):
        if A[i]<B[j]:
            ans[k]=A[i]
            i+=1
        else:
            ans[k]=B[j]
            j+=1
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = mer.popleft()
    B = mer.popleft()
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Solution (Python):
from collections import deque

def merge(A,B):
    ans = [0]*(len(A)+len(B))
    count=i=j=0
    A+=[10**9+1]
    B+=[10**9+1]
    for k in range(len(ans)):
        if A[i]<B[j]:
            ans[k]=A[i]
            i+=1
        else:
            ans[k]=B[j]
            j+=1
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.popleft()
    if(len(d)>2):
        mid = len(d)//2
        div.append(d[:mid])
        div.append(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.append(d[::-1])
        else:
            mer.append(d)
        count+=2
    else:
        mer.append(d)
        
while(len(mer)>1):
    A = mer.pop()
    B = mer.pop()
    ret = merge(A,B)
    mer.appendleft(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)

Solution (Python):
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 = 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):
        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)
        merge(left, mid, right)

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

Solution (Python):
cnt = 0
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [10 ** 10]
    R = A[mid:right] + [10 ** 10]
    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 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

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

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

def merge(A, left, mid, right):
    cnt = 0
    n1 = mid - left
    n2 = right - mid
    L = [0]*(n1+1)
    R = [0]*(n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float("inf")
    R[n2] = float("inf")
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return cnt
            
def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right)//2
        cnt_left = merge_sort(A, left, mid)
        cnt_right = merge_sort(A, mid, right)
        cnt_merge = merge(A, left, mid, right)
        cnt = cnt_left + cnt_right + cnt_merge
    else:
        cnt = 0
    return cnt

cnt = merge_sort(S, 0, n)
print(' '.join( map(str, S) ))
print(cnt)

Solution (Python):
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():
    
    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()

Solution (Python):
cnt = 0
def merge(A, left, mid, right):
  global cnt
  
  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] = 999999999
  R[n2] = 999999999
  i = 0
  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):
  
  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)

Solution (Python):
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(10 ** 9)
    R.append(10 ** 9)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import sys
n = int(input())
s = list(map(int, input().split()))
c = 0
a = 'a'
def merge(A, left, mid, right):
    global c
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxsize)
    R.append(sys.maxsize)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

mergesort(s, 0, n)

for i in range(n-1):
    print(s[i], end=' ')
print(s[n-1])
print(c)

Solution (Python):
import math

def InputData():
    
    sequence_len = int(input())
    sequence = list(map(int, input().split(" ")))

    return sequence_len, sequence

def merge(sequence, left, mid, right):
    global merge_cnt
    n1 = mid - left
    n2 = right - mid
    sequence_left = sequence[left:left + n1]
    sequence_right = sequence[mid:mid + n2]
    sequence_left.append(float('inf'))
    sequence_right.append(float('inf'))

    left_cnt = 0
    right_cnt = 0
    for i in range(left, right):
        merge_cnt += 1
        if sequence_left[left_cnt] <= sequence_right[right_cnt]:
            
            sequence[i] = sequence_left[left_cnt]
            left_cnt += 1
        else:
            
            sequence[i] = sequence_right[right_cnt]
            right_cnt += 1

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

def PrintOut(sequence, merge_cnt):
    print(' '.join( map(str, sequence)))
    print(merge_cnt)

def main():
    global merge_cnt
    [sequence_len, sequence] = InputData()
    merge_cnt = 0
    mergeSort(sequence, 0, sequence_len)
    PrintOut(sequence, merge_cnt)

if __name__=="__main__":
    main()

Solution (Python):
INF = float('inf')

cnt = 0

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

def merge(num_list,left,middle,right):
    global cnt
    left_list  =  num_list[left:middle] + [INF]
    right_list = num_list[middle:right] + [INF]

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

n = int(input())
n_list = list(map(int,input().split()))
merge_sort(n_list,0,len(n_list))
print(' '.join([str(i) for i in n_list]))
print(cnt)

Solution (Python):
INF = float('inf')
cnt = 0
def merge(lst, left, middle, right):
    global cnt
    left_list  = lst[left:middle]+[INF]
    right_list = lst[middle:right]+[INF]
    i,j = 0,0
    for k in range(left, right):
        cnt += 1
        if left_list[i] < right_list[j]:
            lst[k] = left_list[i]
            i += 1
        else:
            lst[k] = right_list[j]
            j += 1
    
def merge_sort(lst, left, right):
    if left+1 < right:
        middle = (left+right)//2
        merge_sort(lst,   left, middle)
        merge_sort(lst, middle, right)
        merge(lst,left, middle, right)

n = int(input())
num_list = list(map(int,input().split()))
merge_sort(num_list,0,n)
print(' '.join([str(i) for i in num_list]))
print(cnt)

Solution (Python):
def merge(A, left, mid, right):
    global cnt
    inf = 10 ** 9
    L = A[left:mid] + [inf]
    R = A[mid:right] + [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)
 
 
n = int(input())
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, n)
 
print(' '.join(str(a) for a in A))
print(cnt)

Solution (Python):









    









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

Solution (Python):
def merge_jibun(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [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
        
        
        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_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)

Solution (Python):
def merge_jibun(A, left, mid, right):
    L = A[left:mid] + [1000000]
    R = A[mid:right] + [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
        
        
        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_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)

Solution (Python):
def merge_jibun(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[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
        
        
        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)

Solution (Python):
def merge_jibun(A, left, mid, right):
    global count
    
    L = A[left:mid] + [10 ** 9]
    R = A[mid:right] + [10 ** 9]
    
    

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

Solution (Python):
def merge_jibun(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[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)

Solution (Python):
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[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)

Solution (Python):

INF = 10000000000

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

	n1 = mid - left
	n2 = right - mid

	L = A[left:mid] + [INF]
	R = A[mid:right] + [INF]
	for i in range(n1):
		L[i] = A[left + i]

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

	i = 0
	j = 0
	cnt = 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

	return cnt

def mergeSort(A,left,right):

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

		return merge(A,left,mid,right)+cnt_l+cnt_r

	return 0

if __name__ == '__main__':

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

	left = 0
	right = len(A)

	count = mergeSort(A,left,right)

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

Solution (Python):
def f(n):return 0 if n<2 else n+f(n/2)+f(n-n/2)
n=f(input())
print " ".join(sorted(raw_input().split(),key=int))
print n

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

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

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

Solution (Python):
def merge(a, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    l = a[left:left + n1] + [sentinel]
    r = a[mid:mid + n2] + [sentinel]
    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)

sentinel = 10 ** 10

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

Solution (Python):
def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [sentinel]
    r = a[mid:right] + [sentinel]
    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)

sentinel = 10 ** 9 + 1

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

Solution (Python):
def merge(a, left, mid, right):
    global count
    l = a[left:mid] + [sentinel]
    r = a[mid:right] + [sentinel]
    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)

sentinel = 1000000001

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

Solution (Python):
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( raw_input() )
arrS = [ int( val ) for val in raw_input().split( ' ' ) ]
cnt = 0
mergeSort( arrS, 0, n )
print( " ".join( map( str, arrS ) ) )
print( cnt )

Solution (Python):
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 )

Solution (Python):
import sys
count = 0

def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxint)
    R.append(sys.maxint)
    i = 0
    j = 0
    for k in xrange(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())
mergeSort(S, 0, n)
print ' '.join(map(str, S))
print count

Solution (Python):


count=0

def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = [0 for i in xrange(n1 + 1)]
    R = [0 for i in xrange(n2 + 1)]
    for i in xrange(n1):
        L[i] = A[left + i]
    for i in xrange(n2):
        R[i] = A[mid + i]
    L[n1] = 1<<32 - 1
    R[n2] = 1<<32 - 1
    i = 0
    j = 0
    for k in xrange(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(raw_input())
    refA = map(int, raw_input().split())
    A = list(refA)
    mergeSort(A, 0, n)
    print " ".join(map(str,A))
    print count