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:
import sys
count = 0

def merge(A, left, mid, right):
    global count
    L = A[left:mid]
    R = A[mid:right]
    L.append(sys.maxint)
    R.append(sys.maxint)
    i = 0
    j = 0
    for k in xrange(left, right):
        count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

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

n = int(raw_input())
S = map(int, raw_input().split())
mergeSort(S, 0, n)
print ' '.join(map(str, S))
print count

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
count=0

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

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) / 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        
if __name__ == "__main__":
    n = int(raw_input())
    refA = map(int, raw_input().split())
    A = list(refA)
    mergeSort(A, 0, n)
    print " ".join(map(str,A))
    print count

Submission status: Accepted

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

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

def main():
    num = raw_input()
    num_list = raw_input().split()
    num_list = map(int, num_list)
    count = merge_sort(num_list, 0, len(num_list), 0)
    num_list =  map(str, num_list)
    print " ".join(num_list)
    print count

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
count = 0 

def merge(data, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid 
    L = []
    R = []
    for i in range(n1):
        L.append(data[left+i])
    for i in range(n2):
        R.append(data[mid+i])
    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]:
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1

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

def main():
    num = raw_input()
    num_list = raw_input().split()
    num_list = map(int, num_list)
    merge_sort(num_list, 0, len(num_list))
    num_list =  map(str, num_list)
    print " ".join(num_list)
    print count

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

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

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


n = sys.stdin.readline()
n = int(n)


count = 0

data = sys.stdin.readline()
data_list = data.split(" ")

for i in range(n):
  data_list[i] = int(data_list[i])

mergeSort(data_list, 0, n)

for i in range(n):
  data_list[i] = str(data_list[i])

print " ".join(data_list)
print count

Submission status: Accepted

Solution code:
import sys

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 i in range(n2):
        R.append(A[mid+i])
    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
        global c
        c += 1


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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    nums = [int(n) for n in lines[1].split(" ")]
    c = 0
    mergeSort(nums, 0, N)
    print " ".join(map(str, nums))
    print c

Submission status: Accepted

Solution code:
count = 0
INFTY = 10 ** 10

def merge(A, left, mid, right):
  global count
  n1 = mid - left;
  n2 = right - mid;

  L = []
  R = []

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

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

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

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)

import sys

n = raw_input()
for line in sys.stdin:
  items = line.strip().split()
  items = map(int, items)
  mergeSort(items, 0, len(items))
  print " ".join(map(str, items))
  print count

Submission status: Accepted

Solution code:
count = 0 

def merge(data, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid 
    L = data[left : mid]
    R = data[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]:
            data[k] = L[i]
            i += 1
        else:
            data[k] = R[j]
            j += 1

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

def main():
    num = raw_input()
    num_list = raw_input().split()
    num_list = map(int, num_list)
    merge_sort(num_list, 0, len(num_list))
    num_list =  map(str, num_list)
    print " ".join(num_list)
    print count

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
count = 0

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

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

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

def margeSort(A,left,right):
    if left+1 < right:
        mid = int((left+right)/2)
        margeSort(A,left,mid)
        margeSort(A,mid,right)
        marge(A,left,mid,right)


n = int(raw_input())
s = raw_input()
A = []
A = map(int,s.split())

margeSort(A,0,n)

A_str = map(str,A)
print(" ".join(list(A_str)))
print count

Submission status: Accepted

Solution code:
m=0
def merge(a,left,mid,right):
    n1=mid-left
    n2=right-mid
    el=range(0,n1+1)
    ar=range(0,n2+1)
    for i in range(n1):
        el[i]=a[left+i]
    for i in range(n2):
        ar[i]=a[mid+i]
    el[n1]=float("inf")
    ar[n2]=float("inf")
    i=0
    j=0
    for k in range(left,right):
        global m
        m+=1
        if(el[i] <= ar[j]):
            a[k] = el[i]
            i=i+1
        else:
            a[k]=ar[j]
            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)
    else:
        if(a[left]>a[right-1]):
            a[left],a[right-1]=a[right],a[left]



n=int(input())
s=raw_input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)

Submission status: Accepted

Solution code:
count = 0 
INFTY = 10 ** 10

def merge(A, left, mid, right):
  global count
  n1 = mid - left;
  n2 = right - mid;

  L = []
  R = []

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

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

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

import sys

n = sys.stdin.readline()
for line in sys.stdin:
  items = line.strip().split()
  items = [ int(x) for x in items ]
  mergeSort(items, 0, len(items))
  print(" ".join(map(str, items)))
  print(count)

Submission status: Accepted

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



n=int(input())
s=input()
a=list(map(int,s.split()))
merge_sort(a,0,n)
a=map(str,a)
print(" ".join(list(a)))
print(m)

Submission status: Accepted

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




if __name__ == "__main__":
    num = int(raw_input())
    num_list = raw_input().strip().split()
    num_list = map(int, num_list)
    mergesort(num_list, 0, len(num_list))
    num_list = map(str, num_list)
    print " ".join(num_list)
    print count

Submission status: Accepted

Solution code:
N = int(raw_input())
count = 0

A_str = raw_input().split()
A = map(int, A_str)

def merge(left, right):
    global count
    sorted_list = []
    l_index = 0
    r_index = 0

    while l_index < len(left) and r_index < len(right):
        count += 1
        if left[l_index] <= right[r_index]:
            sorted_list.append(left[l_index])
            l_index += 1
        else:
            sorted_list.append(right[r_index])
            r_index += 1

    if len(left) != l_index:
        sorted_list.extend(left[l_index:])
        count += len(left[l_index:])
    if len(right) != r_index:
        sorted_list.extend(right[r_index:])
        count += len(right[r_index:])

    return sorted_list 

def mergeSort(A):
    
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

print ' '.join(map(str, mergeSort(A)))
print count

Submission status: Accepted

Solution code:
n = int(raw_input())
A = map(int, raw_input().split(" "))
count = 0

def merge(left, right):
    global count
    
    sorted_list = list()
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            sorted_list.append(left[left_index])
            left_index += 1

        else:
            sorted_list.append(right[right_index])
            right_index += 1
            
        count += 1

    if left:
        sorted_list.extend(left[left_index:])
        count += len(left[left_index:])
    if right:
        sorted_list.extend(right[right_index:])
        count += len(right[right_index:])
        

    return sorted_list


    
def mergeSort(A):
    if len(A) <= 1:
        return A

    mid = len(A) // 2
    left = A[:mid]
    right = A[mid:]

    left = mergeSort(left)
    right = mergeSort(right)

    return list(merge(left, right))

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

Submission status: Accepted

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

def merge(num_list, left, mid, right):
	global count 
	L = list(num_list[left:mid])
	L.append(float("inf"))
	R = list(num_list[mid:right])
	R.append(float("inf"))
	i, j = 0, 0
	for k in range(left, right):
		if L[i] <= R[j]:
			num_list[k] = L[i]
			i += 1
			count += 1
		else:
			num_list[k] = R[j]
			j += 1
			count += 1

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
for i in range(len(l)):
	l[i] = int(l[i])
mergeSort(l, 0, n)

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

Submission status: Accepted

Solution code:
global count
count = 0


def merge(num_list, left, mid, right):
    a = mid - left
    b = right - mid
    L = []
    R = []

    for i in range(a):
        L.append(num_list[left + i])
    for i in range(b):
        R.append(num_list[mid + i])

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

    i = 0
    j = 0
    global count

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


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

    return num_list


if __name__ == "__main__":
    num = raw_input()
    line = raw_input()

    num_list = line.strip().split()
    num_list = map(int, num_list)

    merge_list = mergeSort(num_list, 0, len(num_list))
    merge_list = map(str, merge_list)
    print " ".join(merge_list)
    print count

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_B
def merge_sort(array):
    if len(array) > 1:
        L, countL = merge_sort(array[0:len(array)//2])
        R, countR = merge_sort(array[len(array)//2:])
        return merge(L, R, countL+countR)

    if len(array) == 1:
        return [array, 0]

def merge(L, R, count=0):
    L.append(10**9+1)
    R.append(10**9+1)
    response = []
    i = 0
    j = 0
    for k in range(len(L)-1 + len(R)-1):
        if L[i] <= R[j]:
            response.append(L[i])
            i += 1
            count += 1
        else:
            response.append(R[j])
            j += 1
            count += 1
    return [response, count]

n = int(input())
S = list(map(int, input().split()))
numbers, count = merge_sort(S)
print(*numbers)
print(count)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_B
def merge(array, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = array[left:mid]  + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
    cnt += right - left

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


n = int(input())
S = list(map(int, input().split()))
cnt = 0
sentinel = 10 ** 9 + 1
merge_sort(S, 0, len(S))
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_5_B
def merge(array, left, mid, right):
    global cnt
    L = array[left:mid]  + [sentinel]
    R = array[mid:right] + [sentinel]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
    cnt += right - left

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


n = int(input())
S = list(map(int, input().split()))
cnt = 0
sentinel = 10 ** 9 + 1
merge_sort(S, 0, len(S))
print(*S)
print(cnt)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
    global count
    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
    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)

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

Submission status: Accepted

Solution code:
n = int(raw_input())
S = map(int,raw_input().strip().split(' '))

comp = 0

def merge_sort(S):
    if len(S) <= 1:
        return S
    S1,S2 = split(S)
    return merge(merge_sort(S1),merge_sort(S2))

def split(S):
    mid = len(S)/2
    return S[:mid],S[mid:]

def merge(S1,S2):
    S = []
    S1.append(100000000000)
    S2.append(100000000000)
    global comp
    i = 0
    j = 0
    for k in range(len(S1)+len(S2)-2):
        comp += 1
        if S1[i] <= S2[j]:
            S.append(S1[i])
            i += 1
        else:
            S.append(S2[j])
            j += 1
    return S

sorted_S = merge_sort(S)
for s in sorted_S:
    print s,
print
print comp

Submission status: Accepted

Solution code:
"""Merge Sort."""

def merge(A, left, mid, right):
    """Merge the two sorted partial sequences A[left:mid] and A[mid:right].

    To count the number of comparisons,
    make a global declaration for the variable cnt.
    """
    L = A[left:mid]
    L.append(10**9 + 1)
    R = A[mid:right]
    R.append(10**9 + 1)
    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):
    """Sort elements in list A using Merge Sort algorithm.

    left is the starting index, initially 0.
    right is the value added 1 to the last index, initially the length of A.
    """
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)


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

cnt = 0

mergeSort(S, 0, n)

print(*S)
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
from itertools import count

def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = list(A[left:left+n1]+[float("inf")]), list(A[mid:mid+n2]+[float("inf")])
  i = 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
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)

Submission status: Accepted

Solution code:
def merge(A, left, mid, right):
  global counter
  n1, n2 = mid - left, right - mid
  L, R = list(A[left:left+n1]+[float("inf")]), list(A[mid:mid+n2]+[float("inf")])
  i = j = 0
  for k in range(left, right):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  counter += right - left
def mergeSort(A, left, right):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid)
    mergeSort(A, mid, right)
    merge(A, left, mid, right)

N = int(input())
A = [int(i) for i in input().split()]
counter = 0
mergeSort(A, 0, len(A))
print(*A)
print(counter)

Submission status: Accepted

Solution code:
def merge(a, l, m, r):
    global cnt
    ll = a[l:m] + [1e9 + 1]
    rl = a[m:r] + [1e9 + 1]
    i, j = 0, 0
    for k in range(l, r):
        if ll[i] < rl[j]:
            a[k] = ll[i]
            i += 1
        else:
            a[k] = rl[j]
            j += 1
        cnt += 1


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)


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

Submission status: Accepted

Solution code:
from collections import deque

INFTY = 1e9 + 1


def merge(a, l, m, r):
    global cnt
    ll = deque(a[l:m])
    rl = deque(a[m:r])
    ll.append(INFTY)
    rl.append(INFTY)
    for k in range(l, r):
        a[k] = (ll if ll[0] < rl[0] else rl).popleft()
    cnt += 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)


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

Submission status: Accepted

Solution code:
import math

class MergeSort:
    cnt = 0
    def merge(self, a, n, left, mid, right): 
        n1 = mid - left
        n2 = right - mid
        l = a[left:(left+n1)]
        r = a[mid:(mid+n2)]
        l.append(2000000000)
        r.append(2000000000)
        i = 0
        j = 0
        for k in range(left, right):
            self.cnt += 1
            if l[i] <= r[j]:
                a[k] = l[i]
                i += 1
            else:
                a[k] = r[j]
                j += 1
        return a
        
    def mergeSort(self, a, n, left, right):
        if left + 1 < right:
            mid = (left + right) // 2
            self.mergeSort(a, n, left, mid)
            self.mergeSort(a, n, mid, right)
            self.merge(a, n, left, mid, right)
        return a

if __name__ == '__main__':
    n = int(input().rstrip())
    s = [int(i) for i in input().rstrip().split(" ")]
    x = MergeSort()
    print(" ".join(map(str, x.mergeSort(s, n, 0, n))))
    print(x.cnt)

Submission status: Accepted

Solution code:
n = int(raw_input())
S = map(int, raw_input().split())
cnt = 0

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

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0

def main():
    mergeSort(S, 0, len(S))
    print ' '.join(map(str, S))
    print cnt
    return 0

main()

Submission status: Accepted

Solution code:
n = int(raw_input())
S = map(int, raw_input().split())
cnt = 0

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

def mergeSort(A, left, right):
    if right - left > 1:
        mid = int((left + right) / 2)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    return 0

def main():
    mergeSort(S, 0, len(S))
    print ' '.join(map(str, S))
    print cnt
    return 0

main()

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys

cnt = 0

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

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    S = map(int, lines[1].split())
    mergeSort(S, 0, int(lines[0]))
    print " ".join([str(s) for s in S])
    print cnt

Submission status: Accepted

Solution code:
ct=0
def merge(A,left,mid,right):
    global ct
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append(float('inf'))
    r.append(float('inf'))
    i=0
    j=0
    for k in xrange(left,right):
        ct+=1
        if l[i]<=r[j]:
            A[k]=l[i]
            i=i+1
        else:
            A[k]=r[j]
            j=j+1

def mergesort(A,left,right):
    if left+1<right:
        mid=(left+right)/2
        mergesort(A,left,mid)
        mergesort(A,mid,right)
        merge(A,left,mid,right)
        
n=input()
s=map(int,raw_input().split())
mergesort(s,0,n)
i=0
s=map(str,s)
print(" ".join(s))
print(ct)

Submission status: Accepted

Solution code:
def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    lcount = 0
    rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
            lcount += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        lcount += len(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        rcount += len(right[rpos:])
        
    return merged, lcount + rcount

if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    
    sorted, count = merge_sort(A)
    print ' '.join(str(x) for x in sorted)
    print count

Submission status: Accepted

Solution code:
def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    lcount = 0
    rcount = 0
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
            lcount += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        lcount += len(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        rcount += len(right[rpos:])
        
    return merged, lcount + rcount

if __name__ == '__main__':
    n = int(raw_input())
    A = map(long, raw_input().split())
    
    sorted, count = merge_sort(A)
    print ' '.join(str(x) for x in sorted)
    print count