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:
count = 0
INF = float('inf')
def merge(A, left, mid, right):
    global count
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
    i,  j = 0, 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 =  int((left+right)/2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)



#right は部分配列の末尾+1 の要素を指す。

n = int(input())
A = list(map(int, input().split()))
mergeSort(A, 0, n)
for i in range(n):
    if i>0:
        print(" ", end="")
    print(A[i], end="")
print()
print(count)

Submission status: Accepted

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

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

def solver():
  print(*mergesort(list(map(int,input().split()))))
  print(c)

c = -int(input())


solver()

Submission status: Accepted

Solution code:
INFTY = 1000000001

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

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

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

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

cnt = 0

merge_sort(S, 0, len(S))


print(*S)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    count = 0
    INF = 1000000000000000000000
    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(INF)
    R.append(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 merge_sort(A, left, right):
    if left+1 < right:
        mid = (left + right) // 2
        count_left = merge_sort(A, left, mid)
        count_right = merge_sort(A, mid, right)
        count = merge(A, left, mid, right)
        return count + count_right + count_left
    return 0


def main():
    global A
    n = int(input())
    A = list(map(int, input().split()))
    count = merge_sort(A, 0, len(A))
    print(" ".join([str(a) for a in A]))
    print(count)

main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

count = 0

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

    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = 1.0e+9 + 1
    R[n2] = 1.0e+9 + 1
    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 = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

mergeSort(A, 0, len(A))

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    MAX = 500000
    SENTINEL = 2000000000

    L = [None]*(MAX//2+2)
    R = [None]*(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] = R[n2] = SENTINEL
        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, 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

    n = int(input())

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
S = [int(i) for i in input().split()]

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    i = 0
    j = 0
    L.append(1000000000)
    R.append(1000000000)
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A

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

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

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(i) for i in input().split(" ")]

count = 0

def merge(nums, left, mid, right):
    i = 0
    j = 0
    nums_l = nums[left:mid]
    nums_r = nums[mid:right]
    nums_l.append(10 ** 9 + 1)
    nums_r.append(10 ** 9 + 1)
    for x in range(0, right - left):
        global count
        count = count + 1
        if nums_l[i] <= nums_r[j]:
            nums[left + x] = nums_l[i]
            i = i + 1
        else:
            nums[left + x] = nums_r[j]
            j = j + 1

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

merge_sort(nums, 0, n)
result = ""
for i in nums:
    result += str(i) + " "
print(result.rstrip())
print(count)

Submission status: Accepted

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

    return right - left


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

    return count


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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 1000000000
count = 0
def merge(A, left, mid, right):
  L = A[left:mid] + [INF]
  R = A[mid:right] + [INF]
  global count
  i, j = 0, 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
      count += 1
    else:
      A[k] = R[j]
      j += 1
      count += 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)
  return

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

Submission status: Accepted

Solution code:
count = 0


def merge(A, left, mid, right):
    L = A[left:mid] + [float('INF')]
    R = A[mid:right] + [float('INF')]
    i = 0
    j = 0
    # 右と左比べて小さい方をとってくる
    for k in range(left, right):
        global count
        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()))
mergeSort(A, 0, len(A))
print(*A)
print(count)

Submission status: Accepted

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

def merge(A,left,mid,right,B):
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000000)
    R.append(1000000000)

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

n = int(input())
nums = list(map(int,input().split(" ")))
B = []

mergeSort(nums,0,n,B)
print(' '.join(map(str,nums)))
print(str(len(B)))

Submission status: Accepted

Solution code:
INF = 10 ** 10


def merge(A, left, mid, right):
    count = 0
    L = A[left:mid] + [INF]
    R = A[mid:right] + [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 merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        countL = merge_sort(A, left, mid)
        countR = merge_sort(A, mid, right)
        return merge(A, left, mid, right) + countL + countR
    return 0


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

Submission status: Accepted

Solution code:
count = 0

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


def merge_sort(a):
    if len(a) == 1:
        return [a[0]]
    mid = len(a) // 2
    l1 = merge_sort(a[:mid])
    l2 = merge_sort(a[mid:])
    merged = merge(l1, l2)
    return merged


def merge(l1, l2):
    global count
    len_l1 = len(l1)
    len_l2 = len(l2)
    l1c = l1.copy()
    l2c = l2.copy()

    l1c.append(10 ** 10)
    l2c.append(10 ** 10)

    i = 0
    j = 0
    r = []
    # print("l1", l1)
    # print("l2", l2)
    for k in range(len_l1 + len_l2):
        # print("i", i)
        # print("j", j)
        count += 1
        if l1c[i] <= l2c[j]:
            r.append(l1c[i])
            i += 1
        else:
            r.append(l2c[j])
            j += 1
    return r


r = merge_sort(l)
print(" ".join([str(i) for i in r]))
print(count)

Submission status: Accepted

Solution code:
SENTINEL = 1e+9
t = 0


def Merge(A, left, mid, right):
    global t
    n1 = mid - left
    n2 = right - mid
    L, R = A[left:left+n1], A[mid:mid+n2]
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(left, right):
        t += 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 t
    input()
    A = [int(i) for i in input().split()]
    Merge_Sort(A, 0, len(A))
    print(*A)
    print(t)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


INF = 10000000000
count = 0

def merge(A, left, mid, right):
    global count 
    L = A[left:mid] + [INF]
    R = A[mid:right] + [INF]
      
    i, j = 0, 0
    for k in range(left, right):
        count = count + 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    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)
         
    return 0
          
  
n = int(input())
A = [int(i) for i in input().split()]
#A = list(np.round(np.random.rand(n)*10,0))
count = mergeSort(A, 0, n)
print(*A)
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

def merge(A, left, mid, right):
    global count
    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):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        count += 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().rstrip())
A = list(map(int,input().rstrip().split()))
count = 0
mergeSort(A, 0, n)
print(" ".join(map(str,A)))
print(count)

Submission status: Accepted

Solution code:
cnt = 0

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

    L = A[left:mid]
    R = A[mid:right]
    L.append(10000000000)
    R.append(10000000000)

    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 += 1

def mergesort(A, left, right):
    if left + 1 < right: #if block size >= 2
        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(str(cnt))

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline

MAX = 2e9

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    L.append(MAX)
    R = A[mid:right]
    R.append(MAX)
    merged = []
    index_L = 0
    index_R = 0
    comp_cnt = 0
    for _ in range(n1+n2):
        cand_L = L[index_L]
        cand_R = R[index_R]
        comp_cnt += 1
        if (cand_L < cand_R):
            merged.append(cand_L)
            index_L += 1
        else:
            merged.append(cand_R)
            index_R += 1
    A[left:right] = merged
    return comp_cnt
        
def merge_sort(A, left, right):
    comp_cnt = 0
    if (left + 1 < right):
        # Devide
        mid = (left + right) // 2
        # Solve
        _, cnt = merge_sort(A, left, mid)
        comp_cnt += cnt
        _, cnt = merge_sort(A, mid, right)
        comp_cnt += cnt
        # Conquer
        comp_cnt += merge(A, left, mid, right)
    return A, comp_cnt

def main():
    N = int(input())
    S = list(map(int, input().split()))
    left = 0
    right = len(S)
    merged, cnt = merge_sort(S, left, right)
    print(" ".join([str(x) for x in merged]))
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

INF = 1000000007

def merge(A, l, m, r):
    global count
    L = A[l:m] + [INF]
    R = A[m:r] + [INF]
    li = 0
    ri = 0
    for j in range(l, r):
        count += 1
        if L[li] <= R[ri]:
            A[j] = L[li]
            li += 1
        else:
            A[j] = R[ri]
            ri += 1

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

n = int(stdin.readline().rstrip())
S = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
mergeSort(S, 0, n)
print(*S)
print(count)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    L = A[left:mid] + [2147483648]
    R = A[mid:right] + [2147483648]
    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 c
    c += right - left


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


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

Submission status: Accepted

Solution code:
import sys
from typing import List
import math

n = int(input())
S = [int(i) for i in input().split()]
hikaku = 0


def merge(A: List[int], left: int, mid: int, right: int) -> None:
    global hikaku
    # n1 = mid - left  # left_listのデータ数
    # n2 = right - mid  # right_listのデータ数

    # left_list = [A[left + i] for i in range(n1)]
    # right_list = [A[mid + i] for i in range(n2)]
    left_list = A[left:mid]
    right_list = A[mid:right]
    left_list.append(sys.maxsize)
    right_list.append(sys.maxsize)

    i = 0  # left_listのインデックス
    j = 0  # right_listのインデックス
    for k in range(left, right):
        hikaku += 1
        if left_list[i] <= right_list[j]:
            A[k] = left_list[i]
            i += 1
        else:
            A[k] = right_list[j]
            j += 1


def merge_sort(A: List[int], left: int, right: int) -> int:
    if left + 1 < right:
        mid = math.floor((left + right) / 2)
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


merge_sort(S, 0, len(S))
print(' '.join(map(str, S)))
print(hikaku)

Submission status: Accepted

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

"""
マージソート
・再帰で全部分割してから統合
"""

import sys
def input(): return sys.stdin.readline().strip()

N = int(input())
aN = list(map(int, input().split()))
ans = 0

def merge(l, m, r):
    # 比較回数
    global ans    

    # aNからl～mとm～rの範囲を取り出す
    L = aN[l:m]
    R = aN[m:r]
    # 番兵(最後の要素の処理をしやすくする)
    L.append(float('inf'))
    R.append(float('inf'))

    i = j = 0
    # 前から順番にLとRを比べて、
    # 小さい方からaNに更新かけて添字を進める
    for k in range(l, r):
        if L[i] <= R[j]:
            aN[k] = L[i]
            i += 1
        else:
            aN[k] = R[j]
            j += 1
        ans += 1

def merge_sort(l, r):
    # l==rの時は何もしない
    if l+1 < r:
        # l==r(要素が1つ)になるまで再帰処理で分割する
        m = (l+r) // 2
        merge_sort(l, m)
        merge_sort(m, r)
        # 統合していく
        merge(l, m, r)

merge_sort(0, N)
print(*aN)
print(ans)

Submission status: Accepted

Solution code:
import math
import sys


def merge(a, left, mid, right):
    count = 0

    a1 = a[left:mid] + [math.inf]
    a2 = a[mid:right] + [math.inf]

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

    return count


def merge_sort(a, left, right):
    if left + 1 >= right:
        return 0

    count = 0
    mid = (left + right) // 2
    count += merge_sort(a, left, mid)
    count += merge_sort(a, mid, right)
    count += merge(a, left, mid, right)
    return count


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().split()]
count = merge_sort(a, 0, len(a))

print(' '.join(map(str, a)))
print(count)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global cnt
    inf = 100000000001
    n1, n2 = mid - left, right - mid
    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 = list(map(int, input().strip().split()))
mergeSort(A, 0, n)
print(*A)
print(cnt)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    INF = 1000000001

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

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

n = int(input())
A = list(map(int, input().split()))
left = 0
right = n
cnt = mergeSort(A, left, right)
print(' '.join(map(str, A)))
print(cnt)

Submission status: Accepted

Solution code:
import math
import sys

def merge(nums, left, mid, right):
    sentiel = sys.maxsize

    lefts = [nums[left+i] for i in range(mid - left)]
    lefts.append(sentiel)

    rights = [nums[mid+i] for i in range(right - mid)]
    rights.append(sentiel)

    l = 0
    r = 0
    cnt = 0

    for k in range(left, right):
        if lefts[l] <= rights[r]:
            nums[k] = lefts[l]
            l += 1
        else:
            nums[k] = rights[r]
            r += 1
        cnt += 1

    return nums, cnt

def mergeSort(nums, left, right):
    if right - left <= 1:
        return nums, 0

    mid = left + math.ceil((right - left)/2)

    nums, cntl = mergeSort(nums, left, mid)
    nums, cntr = mergeSort(nums, mid, right)

    nums, cnt  = merge(nums, left, mid, right)

    return nums, cnt+cntl+cntr

def main():
    n = int(input())
    nums = [int(x) for x in input().split(' ')]

    snums, cnt = mergeSort(nums, 0, n)

    print(' '.join([str(x) for x in snums]), cnt, sep="\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def swap(list,i,j,count):
    if(list[j]<list[i]):
        list[i],list[j]=list[j],list[i]
        return 1
    return 0

def merge(list,left1,left2,right2,count):#ソート済みの２つの区間(list[left1]〜list[left2-1]と、list[left2]〜list[right2-1]）を結合する
    i=left1
    j=left2
    tmp_list=[]
    while(1):
        if(list[i] <=list[j]):
            tmp_list.append(list[i])
            i+=1
        else:
            tmp_list.append(list[j])
            j+=1
        if(i==left2):
            for k in range(j,right2):
                tmp_list.append(list[k])
            break
        if(j==right2):
            for k in range(i,left2):
                tmp_list.append(list[k])
            break
    for k in range(left1,right2):
        list[k]=tmp_list[k-left1]
    count[0]+=right2-left1
    

                
                
    
        



def merge_sort(list,left,right,count):#list[left]からlist[right]までの要素でマージソート
    if(right  == left ):
        return None
    if(left+1 == right):
        swap(list,left,right,count)
        count[0]+=2
    else:
        mid=(left + right)//2
        merge_sort(list,left,mid,count)
        merge_sort(list,mid+1,right,count)
        merge(list,left,mid+1,right+1,count)
        

n=int(input())
data=list(map(int,input().split()))
count=[0]
merge_sort(data,0,n-1,count)
print(" ".join(list(map(str,data))))
print(count[0])

Submission status: Accepted

Solution code:
def mergesort(n_list, left, right):
    if left + 1 < right:
        mid = math.ceil((left + right)/2)
        mergesort(n_list, left, mid)
        mergesort(n_list, mid, right)
        merge(n_list, left, mid, right)

def merge(n_list, left, mid, right):
    global c
    n1 = mid - left
    n2 = right - mid
    l_list = n_list[left:mid]
    r_list = n_list[mid:right]
    l_list.append(10e10)
    r_list.append(10e10)
    i = 0
    j = 0
    for k in range(left, right):
        c += 1
        if l_list[i] < r_list[j]:
            n_list[k] = l_list[i]
            i += 1
        else:
            n_list[k] = r_list[j]
            j += 1

        
        

import math
n = int(input())
n_list = list(map(int, input().split()))
c = 0
mergesort(n_list, 0, n)
print(" ".join(map(str, n_list)))
print(c)

Submission status: Accepted

Solution code:
import sys

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]+[SENTINEL]
    R = A[mid:mid+n2]+[SENTINEL]
    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

def MergeSort(A, left, right):
    global ncomp
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
        ncomp += right-left
ncomp=0
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split()))
SENTINEL = max(s)+1
MergeSort(s, 0, n)
print(' '.join(map(str,s)))
print(ncomp)

Submission status: Accepted

Solution code:
import math
n = int(input())
*S, = map(int, input().split())
c = 0

def marge(A, p, q, r):
    # n1 = q - p + 1 # qの要素に関しても加算する必要がある。
    # n2 = r - q
    L, R = A[p: q], A[q: r]
    global c
    L.append(int(10E10))
    R.append(int(10E10))

    i, j = 0, 0
    for k in range(p, r):
        c = c + 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

def marge_sort(A, p, r):
    if p + 1 < r:
        q = math.ceil((p + r) / 2)
        marge_sort(A, p, q)
        marge_sort(A, q, r)
        marge(A, p, q, r)

marge_sort(S, 0, len(S))
print(' '.join(map(str, S)))
print(c)

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from math import inf

c = 0

def merge(A, left, mid, right):
    global c
    
    # print(A, left, mid, right)
    L = A[left:mid]; L.append(inf)
    R = A[mid:right]; R.append(inf)
    # print(L)
    # print(R)
    i = iter(L); l = next(i)
    j = iter(R); r = next(j)
    for k in range(left, right):
        # print(l, r)
        c += 1
        if l < r:
            A[k] = l
            l = next(i)
        else:
            A[k] = r
            r = next(j)

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():
    n = int(input())
    S = [int(x) for x in input().split()]
    merge_sort(S, 0, n)
    print(*S)
    print(c)

main()

Submission status: Accepted

Solution code:
from collections import deque


def merge(a, l, m, r):
    global c
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(10e10)
    rl.append(10e10)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    c += r - l


def merge_sort(a, l, r):
    if l + 1 < r:
        m = (l + r) // 2
        merge_sort(a, l, m)
        merge_sort(a, m, r)
        merge(a, l, m, r)


if __name__ == '__main__':
    n, a, c = int(input()), list(map(int, input().split())), 0
    merge_sort(a, 0, n)
    print(*a)
    print(c)

Submission status: Accepted

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

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

n = int(input())
A = [int(i) for i in input().split()]
print(*merge_sort(A, 0, n), sep=" ")
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math

f = sys.stdin
n = int(f.readline().split()[0])
A = list(map(int, f.readline().split()[:n]))

COUNT = 0

def Merge(A, left, mid, right):
    global COUNT
    if left == right:
        return
    n1 = mid - left
    n2 = right - mid
    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 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, len(A))
print(" ".join(map(str, A)))
print(COUNT)

Submission status: Accepted

Solution code:
count = 0

def merge(a, left, mid, right):
    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
    global count
    count += right - left
    for k in range(left, right):
        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 = [int(i) for i in input().split()]

mergeSort(a, 0, n)

print(' '.join([str(v) for v in a]))
print(count)

Submission status: Accepted

Solution code:
c = 0
def m(L,R):   
    global c
    j = 0
    for l in L:
        while (j < len(R) and R[j] < l):
            yield R[j]
            j += 1
        yield l
    while (j < len(R)):
        yield R[j]
        j += 1
    c += len(L) + len(R)
    
def merge(A):
    global c
    if len(A) == 1:
        return A
    if len(A) == 2:
        c += 2
        a, b = A
        return A if a < b else (b, a)
    mid = len(A)//2
    A[:] = m(merge(A[:mid]), merge(A[mid:]))
    return A
    
n = int(input())
nlist = list(map(int,input().split()))
A = merge(nlist)  
print(*A)
print(c)