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: Wrong Answer

Solution code:
cnt = 0
def merge(array):
    global cnt
    mid = (len(array))
    if mid > 1:
        left = merge(array[:(int)(mid/2)])
        right = merge(array[(int)(mid/2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
                cnt += 1
            else:
                array.append(right.pop(0))
                cnt += 1
        if len(left) != 0:
            array.extend(left)
            cnt += 1
        elif len(right) != 0:
            array.extend(right)
            cnt += 1
    return array

input()

l = merge(list(map(int,input().split())))
[print(l[i],end = ' ') for i in range(len(l)-1)]
print(l[-1])
print(cnt+1)

Submission status: Wrong Answer

Solution code:
cnt = 0
def merge(array):
    global cnt
    mid = (len(array))
    if mid > 1:
        left = merge(array[:(int)(mid/2)])
        right = merge(array[(int)(mid/2):])
        array = []
        while len(left) != 0 and len(right) != 0:
            if left[0] < right[0]:
                array.append(left.pop(0))
                cnt += 1
            else:
                array.append(right.pop(0))
                cnt += 1
        if len(left) != 0:
            array.extend(left)
            cnt += 1
        elif len(right) != 0:
            array.extend(right)
            cnt += 1
    return array

input()

l = merge(list(map(int,input().split())))
[print(l[i],end = ' ') for i in range(len(l)-1)]
print(l[-1])
if len(l)%2 == 0:
    print(cnt+1)
elif len(l)%2 == 1:
    print(cnt+3)

Submission status: Wrong Answer

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

INFTY = 1000000001
cnt = [0]

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

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        print("left:{}, mid:{}, right:{}".format(left, mid, right))
        merge(left, mid, right)
        print(A)

merge_sort(0, N)
print(" ".join(map(str, A)))
print(cnt[0])

Submission status: Wrong Answer

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

INFTY = 1000000001
cnt = [0]

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

def merge_sort(left, right):
    if left+1 < right:
        mid = int((left+right) / 2)
        merge_sort(left, mid)
        merge_sort(mid, right)
        print("left:{}, mid:{}, right:{}".format(left, mid, right))
        merge(left, mid, right)
        print(A)

merge_sort(0, N)
print(" ".join(map(str, A)))
print(cnt[0])

Submission status: Wrong Answer

Solution code:
import math

cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

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

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
print(cnt)

Submission status: Wrong Answer

Solution code:
import math

cnt = 0

def Merge(A, p, q, r):
    n1 = q - p                  # A[p..q-1]の長さ
    n2 = r - q                  # A[q..r-1]の長さ

    # L[0 .. n1] と R[0 .. n2]を作る
    L = []
    for i in range(n1):
        L.append(A[p+i])
    R = []
    for j in range(n2):
        R.append(A[q+j])
    # 配列L, Rの最後に番兵を置く
    L.append(float("inf"))
    R.append(float("inf"))

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

def MergeSort(A, p, r):
    if p + 1 < r:
        q = (p + r)//2
        MergeSort(A, p, q)
        MergeSort(A, q, r)
        Merge(A, p, q, r)



n = int(input())
S = [int(x) for x in input().split()]
MergeSort(S, 0, n)
print(S)
print(cnt)

Submission status: Wrong Answer

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.append( L[l_id] )
            l_id += 1
        else:
            A.append( 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(input())
s = input()
A = []
A = list(map(int,s.split()))

margeSort(A,0,n)

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

Submission status: Wrong Answer

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 mergeSort(A)
print count

Submission status: Wrong Answer

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 mergeSort(A)
print count

Submission status: Wrong Answer

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

comp = 0

def merge_sort(S):
    global comp
    if len(S) <= 1:
        comp += 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 = []
    global comp
    while True:
        if len(S1) == 0:
            S.extend(S2)
            break
        elif len(S2) == 0:
            S.extend(S1)
            break
        else:
            comp += 1
            if S1[0] < S2[0]:
                S.append(S1[0])
                del S1[0]
            else:
                S.append(S2[0])
                del S2[0]
    return S

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

Submission status: Wrong Answer

Solution code:
import math

class MergeSort:
    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):
            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(x.mergeSort(s, n, 0, n))

Submission status: Wrong Answer

Solution code:
def merge(array):
	mid = len(array)
	if mid > 1:
		left = merge(array[:(mid/2)])
		right = merge(array[(mid/2):])
		array = []
		while len(left) != 0 and len(right) != 0:
			if left[0] < right[0]:
				array.append(left.pop(0))
			else:
				array.append(right.pop(0))
		if len(left) != 0:
			array.extend(left)
		elif len(right) != 0:
			array.extend(right)
	return array
n = int(raw_input())
S = map(int,raw_input().split())
print merge(S)

Submission status: Wrong Answer

Solution code:
def merge(array):
	global t
	mid = len(array)
	if mid > 1:
		left = merge(array[:(mid/2)])
		right = merge(array[(mid/2):])
		array = []
		t += 1
		while len(left) != 0 and len(right) != 0:
			t += 1
			if left[0] < right[0]:
				array.append(left.pop(0))
			else:
				array.append(right.pop(0))
		if len(left) != 0:
			array.extend(left)
		elif len(right) != 0:
			array.extend(right)
	return array
n = int(raw_input())
t = 0
S = merge(map(int,raw_input().split()))
for i in xrange(len(S)-1):
	print S[i],
print S[i+1]
print t+1

Submission status: Wrong Answer

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
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
        
    return merged, lpos + rpos

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: Wrong Answer

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
    merged = []
    while lpos < len(left) and rpos < len(right):
        if left[lpos] <= right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
    
    if left[lpos:]:
        merged.extend(left[lpos:])
        lpos += 1
    if right[rpos:]:
        merged.extend(right[rpos:])
        rpos += 1
        
    return merged, lpos + rpos

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: Wrong Answer

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:])
    
    print merged
    #return merged, lcount + rcount
    return merged, len(merged)

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

Submission status: Wrong Answer

Solution code:
def merge(a, left, mid, right):
    global cnt
    l = a[left:mid] + [10**9 + 1]
    r = a[mid:right] + [10**9 + 1]

    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)
    pass


n = int(input())
S = list(map(int, input().split()))
cnt = 0
mergesort(S, 0, n)
print(S)
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
n = int(input())
SENTINEL = 10000000000
COMPAR = 0

A = list(map(int, sys.stdin.readline().split()))

def merge(A, left, mid, right):
    global COMPAR
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(SENTINEL)
    R.append(SENTINEL)

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

Submission status: Wrong Answer

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, S))))
    print(Comp_count)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
# AIZU ONLINE JUDGE
# Introduction to Algorithms and Data Structures
# ALDS1_5_B
# Recursion / Divide and Conquer - Merge Sort

# ?????????????????????????????±??????????????\??????????????¢?????´????????????
# ????????±??????(Divide and Conquer method)?????????????????§????§£?±???§???????????§????????????????°????????????????????????????????????¨???????§£?±????????????¨??§?????????????????????????????¨???????§£?±?????????¨?????????????§£?±???????????????¨???
# ?????????????????´??????????????????????????????????????????????????°????????´???????????????????????????????????????????????¨????????£?????´?????????

# Input
# A     : ??´??????????????????
# left  : ??????????????????????????????????????????????????????
# mid   : right??¨mid???????????????????¬?????????§???????????????
# right : ??????????????????????????????????????????????????????

cnt = 0
def marge(A, left, mid, right):
    global cnt
    # ??????????????????????????????????????????
    n1 = mid-left
    n2 = right-mid

    # L[0..n1],R[0..n2]?????????
    l = []
    r = []
    for i in xrange(n1):
        l.append(A[left+i])
    for i in xrange(n2):
        r.append(A[mid+i])
    l.append(float('inf'))
    r.append(float('inf'))
    i = 0
    j = 0
    for k in xrange(left,right):
        cnt += 1
        if l[i]<=r[j]:
            A[k] = l[i]
            i+=1
        else:
            A[k] = r[j]
            j+=1

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

def main():
    n = input()
    A = map(int,raw_input().split())
    marge_sort(A,0,len(A))
    print A
    print cnt

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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_l[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: Wrong Answer

Solution code:
N = int(input())

A = [int(x) for x in input().split()]
num_c = 0
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if A[j] < A[minj]:
            minj = j
    A[i], A[minj] = A[minj], A[i]
    num_c += 1

print((" ").join(str(x) for x in A))
print(num_c)

Submission status: Wrong Answer

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)
print(num_compare)

Submission status: Wrong Answer

Solution code:
global cnt                                                     
cnt = 0                                                        
def Merge(left, right):                                        
    global cnt                                                 
    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:]                                           
    cnt += 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()                                                
print MergeSort(map(int,                                       
                    raw_input().split())), cnt

Submission status: Wrong Answer

Solution code:
global cnt                                                     
cnt = 0                                                        
def Merge(left, right):                                        
    global cnt                                                 
    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:]                                           
    cnt += 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()                                                
print MergeSort(map(int,                                       
                    raw_input().split())), '\n', cnt

Submission status: Wrong Answer

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] = -1
    R[n2] = -1
    i = 0
    j = 0
    #global cnt
    cnt = 0

    for k in range(left, right):
        if L[i] <= R[j] & L[i]>0:
            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: Wrong Answer

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

if __name__ == "__main__":
  n = int(input())
  S = list(map(int, input().split()))
  cnt = [0]
  mergeSort(S, 0, len(S), cnt)
  print(S)
  print(cnt[0])

Submission status: Wrong Answer

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


if __name__=='__main__':
    A = list(map(int, input().strip().split()))
    count = 0
    merge_sort(A, 0, len(A))
    print(" ".join(map(str, A)))
    print(count)

Submission status: Wrong Answer

Solution code:
def merge(S, left, mid, right):
	global cnt
	S1 = S[:left]
	S2 = S[left:mid][::-1]
	S3 = S[mid:right][::-1]
	S4 = S[right:]
	temp = []
	while S2 and S3:
		cnt += 1
		temp.append(min(S2,S3,key = lambda X:X[-1]).pop())
	temp += S2 + S3
	cnt += (len(S2)+len(S3))
	S[left:right] = temp


def merge_sort(S, left = 0, right = 500000):
	right = min(len(S),right)
	if left+1 < right:
		mid = (left+right) // 2
		merge_sort(S, left, mid)
		merge_sort(S, mid, right)
		merge(S, left, mid, right)


if __name__ == '__main__':
	n = int(input())
	S = [int(s) for s in input().split()]
	cnt = 0
	merge_sort(S)
	print(*S)
	print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

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] = 10**9 + 1
    R[n2] = 10**9 + 2
    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):
    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, n)
print ' '.join(map(str, a))

Submission status: Wrong Answer

Solution code:
import math
import sys

sys.setrecursionlimit(10000)


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

    for i in range(0, mid - left):
        L.append(A[left + i])
    for i in range(0, right - mid):
        R.append(A[mid + i])

    L.append(math.inf)
    R.append(math.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


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())
li = [int(x) for x in input().split(' ')]
mergeSort(li, 0, len(li))
print(*li)

Submission status: Wrong Answer

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

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [None]*(n1+1)
    R = [None]*(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):
        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
        print(A, left, mid, right)
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    
if __name__ == '__main__':

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

    mergeSort(S, 0, n)

    print(" ".join(map(str, S)))
    print(cnt)

Submission status: Wrong Answer

Solution code:
def g(A,l,m,r):
 global c
 L=A[l:m]+[1e10]
 R=A[m:r]+[1e10]
 i=j=0
 for k in range(l,r):
  if L[i]<R[j]:A[k]=L[i];i+=1
  else:A[k]=R[j];j+=1
  c+=1
def s(A,l,r):
 if l+1<r:
  m=(l+r)//2
  s(A,l,m)
  s(A,m,r)
  g(A,l,m,r)
c=0
n=int(input())
A=list(map(int,input().split()))
s(A,0,n)
print(*A)