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: Time Limit Exceeded

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

import sys

_input = sys.stdin.readlines()
array_length = int(_input[0])
array = list(map(int, _input[1].split()))
# print(array_length, array)
assert array_length == len(array)


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

    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1 + 1)]
    R = [0 for _ in range(n2 + 1)]

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

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

    L[n1], R[n2] = [1e9] * 2
    i, j = [0] * 2

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

    return None


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


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Time Limit Exceeded

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

# import sys

#_input = sys.stdin.readlines()
array_length = int(input())
array = list(map(int, input().split()))
# print(array_length, array)
assert array_length == len(array)


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

    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1 + 1)]
    R = [0 for _ in range(n2 + 1)]

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

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

    L[n1], R[n2] = [1e9] * 2
    i, j = [0] * 2

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

    return None


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


if __name__ == '__main__':
    count = 0
    print(*merge_sort(A=array, left=0, right=array_length))
    print(count)

Submission status: Time Limit Exceeded

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

import sys


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

    n1 = mid - left
    n2 = right - mid
    L = [0 for _ in range(n1 + 1)]
    R = [0 for _ in range(n2 + 1)]

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

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

    L[n1], R[n2] = 1e9, 1e9
    i, j = 0, 0

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

    return None


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


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

Submission status: Time Limit Exceeded

Solution code:
counter = 0

def merge(L, R, left, right):
    A = [i for i in range(0,right-left)]
    L.append(float('inf'))
    R.append(float('inf'))

    i,j=(0,0)
    global counter
    for n in range(0,right-left):
        counter = counter+1
        if L[i]<=R[j]:
            A[n]=L[i]
            i=i+1
        else:
            A[n]=R[j]
            j=j+1
    return A

def mergeSort(A, left, right):
    if left+1 < right:
        mid = int((left+right)/2)
        L = mergeSort(A[left:mid],0,mid-left)
        R = mergeSort(A[mid:right],0,right-mid)
        A = merge(L, R, left, right)
    return A

n = int(input())
l = list(map(int,input().split()))
ll = mergeSort(l,0,n)
print(*ll)
print(counter)

Submission status: Time Limit Exceeded

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


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


Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = [int(x) for x in input().split(' ')]
    # S = [8, 5, 9, 2, 6, 3, 7, 1, 10, 4]

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

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

Submission status: Time Limit Exceeded

Solution code:
from array import array

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


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


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

    # ????????????????????????
    merge_sort(A, 0, len(A))

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

Submission status: Time Limit Exceeded

Solution code:
from array import array

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


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


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

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

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

Submission status: Time Limit Exceeded

Solution code:
from ctypes import *

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


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


class DATA(Structure):
    _fields_ = ("d", c_int * 500001),



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

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

    # ???????????????
    txt = ''
    for i in range(num_of_data):
        txt += str(S.d[i])
        txt += ' '
    txt = txt[:-1]
    print('{0}'.format(txt))
    print(Comp_count)

Submission status: Time Limit Exceeded

Solution code:
from array import array

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


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

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



Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = array('I', [int(x) for x in input().split(' ')])

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


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

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

Submission status: Time Limit Exceeded

Solution code:
from array import array

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


def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', [A[left+i] for i in range(n1)])
    R = array('I', [A[mid+j] for j in range(n2)])
    L.append(1000000001)
    R.append(1000000001)

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



Comp_count = 0
if __name__ == '__main__':
    # ??????????????\???
    num_of_data = int(input())
    S = array('I', [int(x) for x in input().split(' ')])

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


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

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

Submission status: Time Limit Exceeded

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


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


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

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

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

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

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



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

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

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

Submission status: Time Limit Exceeded

Solution code:
num_comparisons = 0

def merge(A, left, mid, right):
    global num_comparisons
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    i, j = 0, 0
    for k in range(left, right):
        if i >= len(L):
            A[k] = R[j]
            j += 1
        elif j >= len(R):
            A[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        num_comparisons += 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 = [int(x) for x in input().split()]

merge_sort(A, 0, n)
print(*A)
print(num_comparisons)

Submission status: Time Limit Exceeded

Solution code:

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

    for i in range(n1):
        L.append(A[left + i])

    for j in range(n2):
        R.append(A[mid + j])

    L.append(float("inf"))
    R.append(float("inf"))

    i = 0
    j = 0

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

    return right - left

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        cnt1 = mergeSort(A, left, mid)
        cnt2 = mergeSort(A, mid, right)
        cnt3 = merge(A, left, mid, right)
        return cnt1 + cnt2 + cnt3
    else:
        return 0

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

ans = mergeSort(S, 0, n)

print(*S)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0


def merge_sort(array, l, r):
    if l + 1 < r:
        mid = int((r + l) / 2)
        merge_sort(array, l, mid)
        merge_sort(array, mid, r)
        merge(array, l, mid, r)


def merge(array, l, m, r):
    global cnt
    n1 = m - l
    n2 = r - m
    ary_l = [2E9 for _ in range(n1 + 1)]
    ary_r = [2E9 for _ in range(n2 + 1)]
    for i in range(n1):
        ary_l[i] = array[l + i]
    for i in range(n2):
        ary_r[i] = array[m + i]

    i_l = i_r = 0
    for i in range(r - l):
        cnt += 1
        if ary_l[i_l] <= ary_r[i_r]:
            array[i + l] = ary_l[i_l]
            i_l += 1
        else:
            array[i + l] = ary_r[i_r]
            i_r += 1


if __name__ == '__main__':
    input()
    ary = [int(i) for i in input().rstrip().split()]
    merge_sort(ary, 0, len(ary))
    print(' '.join([str(i) for i in ary]))
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

ary_l = [0] * 250001
ary_r = [0] * 250001


def merge_sort(array, l, r):
    if l + 1 < r:
        mid = int((r + l) / 2)
        merge_sort(array, l, mid)
        merge_sort(array, mid, r)
        merge(array, l, mid, r)


def merge(array, l, m, r):
    global cnt
    global ary_l
    global ary_r
    n1 = m - l
    n2 = r - m
    for i in range(n1):
        ary_l[i] = array[l + i]
    ary_l[n1] = 2E9
    for i in range(n2):
        ary_r[i] = array[m + i]
    ary_r[n2] = 2E9

    i_l = i_r = 0
    for i in range(l, r):
        cnt += 1
        if ary_l[i_l] <= ary_r[i_r]:
            array[i] = ary_l[i_l]
            i_l += 1
        else:
            array[i] = ary_r[i_r]
            i_r += 1


if __name__ == '__main__':
    input()
    ary = [int(i) for i in input().rstrip().split()]
    merge_sort(ary, 0, len(ary))
    print(' '.join([str(i) for i in ary]))
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt = 0

ary_l = [0] * 250001
ary_r = [0] * 250001


def merge_sort(array, l, r):
    if l + 1 < r:
        mid = int((r + l) / 2)
        merge_sort(array, l, mid)
        merge_sort(array, mid, r)
        merge(array, l, mid, r)


def merge(array, l, m, r):
    global cnt
    global ary_l
    global ary_r
    n1 = m - l
    n2 = r - m
    # for i in range(n1):
    #     ary_l[i] = array[l + i]
    ary_l[0:n1] = [i for i in array[l: l + n1]]
    ary_l[n1] = 2E9
    # for i in range(n2):
    #     ary_r[i] = array[m + i]
    ary_r[0:n2] = [i for i in array[m: m + n2]]
    ary_r[n2] = 2E9

    i_l = i_r = 0
    for i in range(l, r):
        cnt += 1
        if ary_l[i_l] <= ary_r[i_r]:
            array[i] = ary_l[i_l]
            i_l += 1
        else:
            array[i] = ary_r[i_r]
            i_r += 1


if __name__ == '__main__':
    input()
    ary = [int(i) for i in input().rstrip().split()]
    merge_sort(ary, 0, len(ary))
    print(' '.join([str(i) for i in ary]))
    print(cnt)

Submission status: Time Limit Exceeded

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

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


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

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

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

Solution code:
def merge(A, l, m, r):
  n1 = m - l
  n2 = r - m
  L = [0] * (n1 + 1)
  R = [0] * (n2 + 1)

  for i in range(n1): L[i] = A[l + i]
  for i in range(n2): R[i] = A[m + i]
  L[n1] = float('inf')
  R[n2] = float('inf')

  i = 0
  j = 0
  count = 0
  for k in range(l, r):
    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, l, r):
  count = 0
  if l + 1 < r:
    m = (l + r) // 2
    count += merge_sort(A, l, m)
    count += merge_sort(A, m, r)
    count += merge(A, l, m, r)
  return count

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

Submission status: Time Limit Exceeded

Solution code:
count = 0
def merge(A,left,mid,right):
    n1 = mid- left
    n2 = right - mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in 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] = float("INFINITY")
    R[n2] = float("INFINITY")
    i = 0
    j = 0
    for k in range(left,right):
        global count 
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            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,n)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

	L = [0 for i in range(n1)]
	R = [0 for i in range(n2)]

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

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

	num_compare += right - left
	for k in range(left, right):
		if j >= n2:
			A[k] = L[i]
			i += 1
		elif i < n1 and L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return num_compare

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

	return num_compare


#fin = open("test.txt", "r")
fin = sys.stdin



n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)

Submission status: Time Limit Exceeded

Solution code:
import sys

def merge(A, left, mid, right, num_compare):
	n1 = mid - left
	n2 = right - mid

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

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

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

	num_compare += 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
	return num_compare

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

	return num_compare


#fin = open("test.txt", "r")
fin = sys.stdin

SENTINEL = float("inf")

n = int(fin.readline())
S = list(map(int, fin.readline().split()))

num_compare = 0
num_compare = merge_sort(S, 0, n, num_compare)

print(S[0], end = "")
for s in S[1:]:
	print(" " + str(s), end = "")
print("") 
print(num_compare)

Submission status: Time Limit Exceeded

Solution code:
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    
    L = [0 for i in range(n1+1)]
    R = [0 for i in 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]=1000000001
    R[n2]=1000000001

    cnt1 = 0
    cnt2 = 0
    
    for k in range(left, right):
        if L[cnt1] <= R[cnt2]:
            A[k] = L[cnt1]
            cnt1 += 1
        else:
            A[k] = R[cnt2]
            cnt2 +=  1
    
    global cnt
    cnt += cnt1 + cnt2
    
    
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().rstrip())
A = list(map(int,input().split(" ")))
cnt = 0
mergeSort(A, 0 , len(A))
print(" ".join(list(map(str,A))))
print(str(cnt))

Submission status: Time Limit Exceeded

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


def merge(ns, left, mid, right):
    global count
    infinity = 10 ** 9
    n1 = mid - left
    n2 = right - mid
    left_ns = [e for e in range(n1 + 1)]
    right_ns = [e for e in range(n2 + 1)]

    for i in range(n1):
        left_ns[i] = ns[left + i]
    for i in range(n2):
        right_ns[i] = ns[mid + i]
    
    left_ns[n1] = infinity
    right_ns[n2] = infinity

    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if left_ns[i] <= right_ns[j]:
            ns[k] = left_ns[i]
            i += 1
        else:
            ns[k] = right_ns[j]
            j += 1


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

n = int(input())
ns = [int(e) for e in input().split()]
left = 0
right = len(ns)
count = 0
merge_sort(ns, left, right)
ns = [str(n) for n in ns]

print(" ".join(ns))
print(count)

Submission status: Time Limit Exceeded

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

infinity = pow(10, 9) + 1


def merge(ns, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    left_ns = [e for e in range(n1 + 1)]
    right_ns = [e for e in range(n2 + 1)]

    for i in range(n1):
        left_ns[i] = ns[left + i]
    for i in range(n2):
        right_ns[i] = ns[mid + i]
    
    left_ns[n1] = infinity
    right_ns[n2] = infinity

    i = 0
    j = 0
    for k in range(left, right):
        count += 1
        if left_ns[i] <= right_ns[j]:
            ns[k] = left_ns[i]
            i += 1
        else:
            ns[k] = right_ns[j]
            j += 1


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


n = int(input())
ns = [int(e) for e in input().split()]
left = 0
right = len(ns)
count = 0
merge_sort(ns, left, right)
# ns = [str(n) for n in ns]

print(*ns)
print(count)

Submission status: Time Limit Exceeded

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

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

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

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

Submission status: Time Limit Exceeded

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

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

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

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

Submission status: Time Limit Exceeded

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

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

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

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