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: WA: Presentation Error

Solution code:
global cmt                                                     
cmt = 0                                                        
def Merge(left, right):                                        
    global cmt                                                 
    lst = []                                                   
    i, j = 0, 0                                                
    while i < len(left) and j < len(right):                    
        if left[i] <= right[j]:                                
            lst.append(left[i])                                
            i += 1                                             
        else:                                                  
            lst.append(right[j])                               
            j += 1                                             
    lst += left[i:]                                            
    lst += right[j:]                                           
    cmt += len(lst)                                            
                                                               
    return lst                                                 
                                                               
def MergeSort(A):                                              
    if len(A) == 1: return A                                   
    mid = len(A) / 2                                           
    left = MergeSort(A[:mid])                                  
    right = MergeSort(A[mid:])                                 
    #print left, right                                         
    sortedList = Merge(left, right)                            
    return sortedList                                          
                                                               
n = raw_input()                                                
output = ''                                                    
for n in MergeSort(map(int, raw_input().split())):             
    output += str(n) + ' '                                     
print output, '\n', cmt

Submission status: WA: Presentation Error

Solution code:
global cmt                                                     
cmt = 0                                                        
def Merge(left, right):                                        
    global cmt                                                 
    lst = []                                                   
    i, j = 0, 0                                                
    while i < len(left) and j < len(right):                    
        if left[i] <= right[j]:                                
            lst.append(left[i])                                
            i += 1                                             
        else:                                                  
            lst.append(right[j])                               
            j += 1                                             
    lst += left[i:]                                            
    lst += right[j:]                                           
    cmt += len(lst)                                            
                                                               
    return lst                                                 
                                                               
def MergeSort(A):                                              
    if len(A) == 1: return A                                   
    mid = len(A) / 2                                           
    left = MergeSort(A[:mid])                                  
    right = MergeSort(A[mid:])                                 
    #print left, right                                         
    sortedList = Merge(left, right)                            
    return sortedList                                          
                                                               
n = raw_input()                                                
output, i = '', 0                                              
for n in MergeSort(map(int, raw_input().split())):             
    output += str(n) if i == 0 else ' ' + str(n)               
    i += 1                                                     
print output, '\n', cmt

Submission status: WA: Presentation Error

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 = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])

    L.append(float("inf"))
    R.append(float("inf"))
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    count += 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)

mergeSort(A,0,N)
ans = ""
for i in A:
    ans += str(i) + " "

print(ans)
print(count)

Submission status: WA: Presentation Error

Solution code:
import sys

def conquer(left,right,List):
    l = r = 0
    result = []
    while l < len(left) and r < len(right):
        List.append(1)
        if left[l] > right[r]:
            result.append(right[r])
            r += 1
        else:
            result.append(left[l])
            l += 1
    while l < len(left):
        List.append(1)
        result.append(left[l])
        l += 1
    while r < len(right):
        List.append(1)
        result.append(right[r])
        r += 1
    return result

def divide(data,List):
    if len(data) <= 1:
        return data
    return conquer(divide(data[0:int((0 + len(data)) / 2)],List),divide(data[int((0 + len(data)) / 2):],List),List)

def mergesort(data):
    temp = []
    result = divide(data,temp)
    for data in result:
        print(data,end=' ')
    print()
    print(sum(temp))

for i in sys.stdin:
    temp = i.split()
    if len(temp) > 1:
        break
for i in range(0,len(temp)):
    temp[i] = int(temp[i])
mergesort(temp)

Submission status: WA: Presentation Error

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

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

Submission status: WA: Presentation Error

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

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

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    print(S[i],end=" ")
print()
print(cnt)

Submission status: WA: Presentation Error

Solution code:

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

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

n=int(input())
S=input().split()
cnt=0
for i in range(n):
    S[i]=int(S[i])
cnt=mergeSort(S,0,n,cnt)
for i in range(n):
    print(S[i],end=" ")
print("")
print(cnt)

Submission status: WA: Presentation Error

Solution code:
def merge_sort(A,cnt):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = A[:mid]
    cnt.append(1)
    right = A[mid:]
    left = merge_sort(left,cnt)
    right = merge_sort(right,cnt)
    return merge(left,right,cnt)
def merge(left, right,cnt):
    merged = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        cnt.append(1)
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if i < len(left):
        merged.extend(left[i:])
    if j < len(right):
        merged.extend(right[j:])
    return merged

n=int(input())
A=[0 for i in range(n)]
A=input().split()
cnt=[]
for i in range(n):
    A[i]=int(A[i])
left=0
right=n
A=merge_sort(A,cnt)
for i in range(n):
    print(A[i],end="")
print(" ")
print(len(cnt)+1)

Submission status: WA: Presentation Error

Solution code:
def merge_sort(A,cnt):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = A[:mid]
    cnt.append(1)
    right = A[mid:]
    left = merge_sort(left,cnt)
    right = merge_sort(right,cnt)
    return merge(left,right,cnt)
def merge(left, right,cnt):
    merged = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        cnt.append(1)
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if i < len(left):
        merged.extend(left[i:])
    if j < len(right):
        merged.extend(right[j:])
    return merged

n=int(input())
A=[0 for i in range(n)]
A=input().split()
cnt=[]
for i in range(n):
    A[i]=int(A[i])
left=0
right=n
A=merge_sort(A,cnt)
for i in range(n):
    print(A[i],"",end="")
print(" ")
print(len(cnt)+1)

Submission status: WA: Presentation Error

Solution code:
def merge_sort(A,cnt):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = A[:mid]
    cnt.append(1)
    right = A[mid:]
    left = merge_sort(left,cnt)
    right = merge_sort(right,cnt)
    return merge(left,right,cnt)
def merge(left, right,cnt):
    merged = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        cnt.append(1)
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    if i < len(left):
        merged.extend(left[i:])
    if j < len(right):
        merged.extend(right[j:])
    return merged

n=int(input())
A=[0 for i in range(n)]
A=input().split()
cnt=[]
for i in range(n):
    A[i]=int(A[i])
left=0
right=n
A=merge_sort(A,cnt)
for i in range(n):
    print(A[i],"",end="")
print(" ")
c=len(cnt)+1
print(c)

Submission status: WA: Presentation Error

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    n1 = mid - left
    n2 = right - mid

    l = []
    for i in range(n1):
        l.append(a[left + i])
    r = []
    for i in range(n2):
        r.append(a[mid + i]) 
    l.append(INF)
    r.append(INF)
    i = 0 
    j = 0 

    ans = 0 

    for k in range(left, right):
        ans += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
    
    return ans 


def merge_sort(a, left, right):
    ans = 0 
    if left + 1 < right:
        mid = (left + right) // 2;
        ans += merge_sort(a, left, mid)
        ans += merge_sort(a, mid, right)
        ans += merge(a, left, mid, right)
    return ans 


def print_list_split_whitespace(s):
    for x in s:
        print(x, end=" ")
    print()

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

ans = merge_sort(s, 0, len(s))

print_list_split_whitespace(s)
print(ans)

Submission status: WA: Presentation Error

Solution code:
def merge(a, left, mid, right):
    INF = int(1e+11)
    n1 = mid - left
    n2 = right - mid

    l = []
    for i in range(n1):
        l.append(a[left + i])
    r = []
    for i in range(n2):
        r.append(a[mid + i])
    l.append(INF)
    r.append(INF)
    i = 0
    j = 0

    ans = 0

    for k in range(left, right):
        ans += 1
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else:
            a[k] = r[j]
            j += 1
    
    return ans


def merge_sort(a, left, right):
    ans = 0
    if left + 1 < right:
        mid = (left + right) // 2;
        ans += merge_sort(a, left, mid)
        ans += merge_sort(a, mid, right)
        ans += merge(a, left, mid, right)
    return ans


def print_list_split_whitespace(s):
    for x in s:
        print(x, end=" ")
    print()

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

ans = merge_sort(s, 0, len(s))

print_list_split_whitespace(s)
print(ans)

Submission status: WA: Presentation Error

Solution code:

count = 0

def merge_sort(arr):
	merge_sort_(arr, 0, len(arr) - 1)

def merge_sort_(arr, floor, ceiling):
	if floor < ceiling:
		mid = int(floor + (ceiling - floor) / 2)
		merge_sort_(arr, floor, mid)
		merge_sort_(arr, mid + 1, ceiling)
		merge(arr, floor, mid, ceiling)

def merge(arr, floor, mid, ceiling):
	global count
	temp_arr = [0] * len(arr)
	for i in range(floor, ceiling + 1):
		temp_arr[i] = arr[i]
	
	i = floor
	j = mid + 1
	k = floor
	while k <= ceiling:
		count += 1
		if j > ceiling or (i <= mid and temp_arr[i] <= temp_arr[j]):
			arr[k] = temp_arr[i]
			i += 1
		else:
			arr[k] = temp_arr[j]
			j += 1
		k += 1
		
n = int(input())
arr = list(map(int, input().split()))
merge_sort(arr)
for i in range(n):
	print(arr[i], end="")
	if i != n:
		print(" ", end="")
print()
print(count)