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):
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

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

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Solution (Python):
def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

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

global S
n = int(raw_input())
S = map(int, raw_input().split())

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Solution (Python):
def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

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

global S
n = int(raw_input())
S = map(int, raw_input().split())

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Solution (Python):
def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

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

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c

Solution (Python):

from __future__ import division, print_function
from sys import stdin

num_swap = 0


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


stdin.readline()
s = [int(s) for s in stdin.readline().split()]
merge_sort(s, 0, len(s))
print(*s)
print(num_swap)

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 = 1000000001
n = int(input())
a = list(map(int, input().strip().split()))
count = 0
merge_sort(a, 0, len(a))
print(' '.join(map(str, a)))
print(count)

Solution (Python):
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid] + [10000000000]
    R = A[mid:right] + [10000000000]

    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)


n = int(input())
lst = list(map(int, input().split()))
cnt = 0

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

Solution (Python):
import sys
input = sys.stdin.readline

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

def Merge(S, l, m, r):
    global cnt
    cnt += r - l
    L = S[l:m] + [float('inf')]
    R = S[m:r] + [float('inf')]
    i, j = 0, 0
    for k in range(l, r):
        if L[i] < R[j]:
            S[k] = L[i]
            i += 1
        else:
            S[k] = R[j]
            j += 1
    return

def MergeSort(S, l, r):
    if r - l > 1:
        m = (l + r) // 2
        MergeSort(S, l, m)
        MergeSort(S, m, r)
        Merge(S, l, m, r)
    return

MergeSort(L, 0, n)
print(*L)
print(cnt)

Solution (Python):
N_MAX = 1000000000

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

mergeCnt = 0

def merge(A, left, mid, right):
    
    global mergeCnt
    
    n1 = mid - left
    n2 = right - mid
    
    L = A[left:mid]
    R = A[mid:right]
    
    L.append(N_MAX)
    R.append(N_MAX)
    
    i = j = 0
    
    for k in range(left, right):
        mergeCnt += 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__'):
    
    left = 0
    right = n
    
    mergeSort(S, left,right)
    
    print(*S)
    print(mergeCnt)

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

def marge(l,r):
    count = 0
    conq = []
    i = 0
    j = 0
    k = len(l) + len(r)
    l.append(float('inf'))
    r.append(float('inf'))
    for o in range(k):
        if l[i] <= r[j]:
            conq.append(l[i])
            i += 1
        else:
            conq.append(r[j])
            j += 1
        count += 1
    return conq,count
           
def margeSort(s):
    n = len(s)
    if n == 1:
        return s,0
    else:
        L, cnt_L = margeSort(s[:n//2])
        R,cnt_R = margeSort(s[n//2:])
        s,cnt = marge(L,R)         
    return s,cnt+cnt_R+cnt_L
S,count = margeSort(S)
print(*S)
print(count)

Solution (Python):
n = int(input())
S = [*map(int, input().split())]

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = list(range(n1+1))
    R = list(range(n2+1))
    
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
        
    L[n1] = 100000000000
    R[n2] = 100000000000
    
    i = 0
    j = 0
    
    for k in range(left, right):
        if L[i] < R[j]:
            A[k] = L[i]
            i = i + 1
            
        else:
            A[k] = R[j]
            j = j + 1
            
    return right - left
            
def mergeSort(A, left, right):
    count = 0
    if left+1 < right:
        mid = int((left + right) / 2)
        count += mergeSort(A, left, mid) + mergeSort(A, mid, right)
        count += merge(A, left, mid, right)

    return count

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

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

Solution (Python):
def merge(a,left,mid,right):
    count=0
    L=a[left:mid]+[float("inf")]
    R=a[mid:right]+[float("inf")]
    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 count

def mergeSort(a,left,right):
    if left+1<right:
        mid=(left+right)//2
        countl=mergeSort(a,left,mid)
        countr=mergeSort(a,mid,right)
        return merge(a,left,mid,right)+countl+countr
    return 0



n=int(input())
a=list(map(int,input().split()))
ans=mergeSort(a,0,n)
print(" ".join(map(str,a)))
print(ans)

Solution (Python):
count = 0


def main():
    input()
    A = [int(x) for x in list(input().split())]
    merge_sort(A, 0, len(A))
    print(*A)
    print(count)


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


if __name__ == '__main__':
    main()

Solution (Python):
num = int(input())
arr = list(map(int, input().split()))

def merge(arr, left, middle, right, count):
    L = arr[left:middle]
    L.append(float('inf'))
    R = arr[middle:right]
    R.append(float('inf'))

    iterL, iterR = iter(L), iter(R)
    l,r = next(iterL), next(iterR)

    for index in range(left, right):
        count += 1
        if l <= r:
            arr[index] = l
            l = next(iterL)
        else:
            arr[index] = r
            r = next(iterR)
    return count

def merge_sort(arr, left, right, count):

    if left + 1 < right:
        pivot = (left + right) // 2
        count = merge_sort(arr, left,  pivot, count)
        count = merge_sort(arr, pivot, right, count)

        count = merge(arr, left, pivot, right, count)
    return count

count = merge_sort(arr, 0, num, 0)
print(" ".join(list(map(str, arr))))
print(count)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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


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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    cnt = merge_sort(A, 0, N)
    print(*A)
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
def merge(A, left, mid, right):
    global counter
    INFTY = 10 ** 10
    L = A[left:mid]
    R = A[mid:right]
    L.append(INFTY)
    R.append(INFTY)
    i, j = 0, 0
    for k in range(left, right):
        counter += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)
        
n = int(input())
A = list(map(int, input().split()))

counter = 0
merge_sort(A, 0, n)
print(' '.join(str(a) for a in A))
print(counter)

Solution (Python):
import math

def merge(a,l,m,r):
    global cnt
    L = a[l:m]+[math.inf]
    R = a[m:r]+[math.inf]
    i = 0
    j = 0
    for k in range(l,r):
        cnt+=1
        if L[i]<=R[j]:
            a[k] = L[i]
            i+=1
        else:
            a[k]=R[j]
            j+=1
def mergeSort(a,l,r):
    if l+1<r:
        m = (l+r)//2
        mergeSort(a,l,m)
        mergeSort(a,m,r)
        merge(a,l,m,r)
n = int(input())
a = list(map(int, input().split()))
cnt = 0

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

Solution (Python):
import math


def merge(S, left, mid, right) -> int:
    
    
    L = S[left: mid]
    R = S[mid: right]

    
    
    L.append(math.inf)

    
    
    R.append(math.inf)

    i = 0
    j = 0

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

    return right - left


def merge_sort(S, left, right):
    count = 0

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

    return count


def main():
    n = int(input())
    S = list(map(int, input().split()))
    count = 0

    count = merge_sort(S, 0, n)

    print(*S)
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
counter = 0


def merge(A, left, mid, right):
    m = mid - left
    n = right - mid
    L = [None] * (m+1)
    R = [None] * (n+2)

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

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

    L[m], R[n] = float("inf"), float("inf")  
    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
    global counter
    counter += right - left
    return


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


def main():
    _ = input()
    A = [int(i) for i in input().strip().split()]
    merge_sort(A, 0, len(A))
    print(" ".join([str(i) for i in A]))


if __name__ == "__main__":
    counter = 0
    main()
    print(counter)

Solution (Python):
import math
inf = math.inf

def merge(A, left, mid, right):
    global cnt
    
    L = []
    R = []
    for i in A[left:mid]:
        L.append(i)
    for i in A[mid:right]:
        R.append(i)
    L.append(inf)
    R.append(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 right - left > 1:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

_ =input()
A = list(map(int, input().rstrip().split(" ")))
cnt = 0
mergeSort(A, 0, len(A))

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

Solution (Python):
import sys
input = sys.stdin.readline

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

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

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

Solution (Python):
import sys

INF = 10**9

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]

z = 0


def merge(A, left, right):

    global z

    n1 = (right - left) // 2 + left  

    
    
    

    L = A[left:n1]
    R = A[n1:right]


    L.append(INF)
    R.append(INF)

    

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


mergesort(A, 0, N)

print(" ".join([str(x) for x in A]))
print(z)

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

from sys import stdin

n = int(stdin.readline().rstrip())
*A, = map(int, stdin.readline().split())
cnt = 0

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    L.append(10 ** 9)
    R.append(10 ** 9)
    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
    global cnt
    cnt += 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)

merge_sort(A, 0,n)
print(" ".join(map(str, A)))
print(cnt)

Solution (Python):

"""
ソートテク関連の基本的な関数の詰め合わせ (命名は C++ STL algorithm による)


stable_partition(seq, func):
    O(n)
    空間計算量も O(n)
    述語が True を返す全ての要素が、述語が False を返す全ての要素よりも前になるようにシーケンスを並び替える (破壊、安定)


nth_element(seq, k, begin, end):
    O(n)
    E = seq[k] とする
    特定の要素 E よりも小さい全ての要素が E よりも前になり、 E 以上の全ての要素がEよりも後になるように seq[begin:end] を並び替える (破壊、不安定)
    heapq の nlargest とは異なるので注意


ith_order_statistic(seq, i, begin, end):
    O(n)
    nth_element を用いて (seq[begin:end] に存在することがわかっている) i 番目の順序統計量を求める (i = 0, 1, ..., n-1)


simple_quick_sort(seq, begin, end):
    O(nlgn)
    nth_element を用いて seq[begin:end] をソートする (破壊、不安定)


modified_merge_sort(seq, begin, end):
    O(nlgn)
    _modified_merge を用いて seq[begin:end] をソートする (非破壊、安定)
    転倒数とソート済み配列を返す


count_inversion(seq):
    O(nlgn)
    modified_merge_sort を用いて seq の転倒数を求める
    (転倒数: seq[i] > seq[j] (i < j) なる (i, j) の組み合わせの数のこと)
"""


import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




def _modified_merge(left: List[Num], right: List[Num]) -> Tuple[int, List[Num]]:
    """
    ソート済み配列 left, right を受け取り、全体のソート済み配列を生成する (O(n))
    マージの過程で転倒数をメモして返す

    Args:
        left (list): ソート済み
        right (list): ソート済み

    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> _modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])
    """
    sorted_list = []
    i, j, inv = 0, 0, 0
    buf_1 = left[:] + [float('inf')]
    buf_2 = right[:] + [float('inf')]
    for _ in range(len(left) + len(right)):
        if buf_1[i] < buf_2[j]:
            sorted_list.append(buf_1[i])
            i += 1
        else:
            sorted_list.append(buf_2[j])
            j += 1
        inv += 1
    return inv, sorted_list


def modified_merge_sort(L, begin, end):
    """
    L[begin:end] を 非破壊的かつ安定にマージソートする (O(nlgn))
    マージソートの過程で転倒数をメモして返す

    Args:
        L (list)
        begin, end (int)
    
    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])
    """
    if end - begin == 1:
        return 0, [L[begin]]
    mid = (begin + end) // 2
    left_inv_cnt, left = modified_merge_sort(L, begin, mid)
    right_inv_cnt, right = modified_merge_sort(L, mid, end)
    merge_inv_cnt, sorted_list = _modified_merge(left, right)
    return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list





def count_inversion(L):
    """
    modified_merge_sort() を用いて L の要素の転倒数を求める (O(nlgn))

    Examples:
        >>> count_inversion([1, 9, 2, 7, 5, 6, 4, 8, 3, 0])
        26
    """
    cnt, _ = modified_merge_sort(L, 0, len(L))
    return cnt



if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    num, seq = modified_merge_sort(L, 0, n)
    print(*seq, sep=' ')
    print(num)

Solution (Python):
n = int(input())
s = list(map(int, input().split()))
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
    global cnt
    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)
        
mergeSort(s, 0, n)
print(' '.join(map(str, s)))
print(cnt)

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

def solve(A):
    left = 0
    right = len(A)
    mergeSort(A, left, right)

def resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    solve(A)
    print(*A)
    print(cnt)

resolve()

Solution (Python):
def merge(cnt, A, left, mid, right):
    L = A[left:mid] + [1e+99]
    R = A[mid:right] + [1e+99]
    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
    cnt.append(right - left)

            
def mergeSort(cnt, A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        mergeSort(cnt, A, left, mid)
        mergeSort(cnt, A, mid, right)
        merge(cnt, A, left, mid, right)
        
        
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n = int(input())
S = list(map(int, input().split()))

from collections import deque
cnt = deque()
mergeSort(cnt,S,0,n)

print(*S)
print(sum(cnt))

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

Solution (Python):
def merge(A, n ,left, mid, right):
    cnt = 0
    L = A[left:mid] + [float("inf")]
    R = A[mid:right] + [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
    return cnt

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

n = int(input())

A = list(map(int, input().split()))

cnt = mergeSort(A, n, 0, n)

print(*A)
print(cnt)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    S = LI()

    cnt = [0]

    def merge(A, left, mid, right):
        L = A[left:mid]
        R = A[mid:right]
        L.append(INF)
        R.append(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
            cnt[0] += 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)
    print(*S)
    print(cnt[0])

if __name__ == '__main__':
    resolve()

Solution (Python):


INFTY = int(1E20)
count = 0


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

    L = [i for i in A[left:mid]]
    R = [i for i in A[mid:right]]

    L.append(INFTY)
    R.append(INFTY)

    idx_L = 0
    idx_R = 0
    for idx in range(left, right):
        count += 1
        if L[idx_L] <= R[idx_R]:
            A[idx] = L[idx_L]
            idx_L += 1
        else:
            A[idx] = R[idx_R]
            idx_R += 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)
    else:
        return


if __name__ == "__main__":
    n = int(input())
    A = [int(i) for i in input().split()]

    mergeSort(A, 0, n)

    print(' '.join([str(i) for i in A]))

    print(count)

Solution (Python):
import sys
input = sys.stdin.readline
MAX = 500000
SENTINEL = 2000000000
L = [0]*(MAX//2 + 2)
R = [0]*(MAX//2 + 2)
cnt = 0

def Merge(A,n,left,mid,right,cnt):
    n1 = mid - left
    n2 = right - mid
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = SENTINEL
    R[n2] = SENTINEL
    L_i = 0
    R_i = 0
    for k in range(left,right):
        cnt += 1
        if L[L_i] <= R[R_i]:
            A[k] = L[L_i]
            L_i += 1
        else:
            A[k] = R[R_i]
            R_i += 1
    return cnt

def MergeSort(A,n,left,right,cnt):
    if left + 1 < right:
        mid = (left + right)//2
        cnt = MergeSort(A,n,left,mid,cnt)
        cnt = MergeSort(A,n,mid,right,cnt)
        cnt = Merge(A,n,left,mid,right,cnt)
    return cnt

if __name__ == "__main__":
    n = int(input())
    array = list(map(int,input().split()))
    cnt = 0
    SENTINEL = 2*10**9
    cnt = MergeSort(array,n,0,n,cnt)
    print(" ".join(map(str,array)))
    print(cnt)