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: Runtime Error

Solution code:
import math
SEN = 500001
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [SEN]
    R = a[mid:right] + [SEN]
    i=0
    j=0
    for k in range(left, right):
        counter += 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 = math.ceil((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(*a)
print(counter)

Submission status: Runtime Error

Solution code:
import math
sentinel = 1e9 + 1
counter = 0
def merge(a, left, mid, right):
    global counter
    L = a[left:mid] + [SEN]
    R = a[mid:right] + [SEN]
    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
    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 = list(map(int, input().split()))
mergeSort(a, 0, n)
print(*a)
print(counter)

Submission status: Runtime Error

Solution code:
def merge(A, left, mid, right):
	global count
	n1 = mid - left
	n2 = right - mid
	L=[]
	R=[]
	for i in range(n1-1):
		L[i] = append(A[left + i])
	for i in range(n2-1):
		R[i] =append(A[mid + i])
	L[n1] = 10e10
	R[n2] = 10e10
	i = 0
	j = 0
	for k in range(left , right-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())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, len(A))
print(*A)
print(count)

Submission status: Runtime Error

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

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)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))
c = 0

mergeSort(S, 0, n)

print(S)
print(c)

Submission status: Runtime 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): 
        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)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))
c = 0

mergeSort(S, 0, n)

print(S)
print(c)

Submission status: Runtime 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): 
        if L[i] <= R[j]:
            c = c+1
            A[k] = L[i]
            i = i + 1
        else:
            c = c+1
            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)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))
c = 0

mergeSort(S, 0, n)

print(S)
print(c)

Submission status: Runtime Error

Solution code:
c = 0

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): 
        if L[i] <= R[j]:
            c = c+1
            A[k] = L[i]
            i = i + 1
        else:
            c = c+1
            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)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))


mergeSort(S, 0, n)

print(S)
print(c)

Submission status: Runtime Error

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

def mergeSort(A, left, right, c):
  if left+1 < right:
    mid = (left + right)//2;
    mergeSort(A, left, mid, c)
    mergeSort(A, mid, right, c)
    merge(A, left, mid, right, c)
    
### Main Function
n = int(input())
S = list(map(int,input().split()))


mergeSort(S, 0, n, c)

print(S)
print(c)

Submission status: Runtime Error

Solution code:
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(len(cnt)+1)

Submission status: Runtime 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:])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)
    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: Runtime Error

Solution code:
def merge(s,left,mid,right):
	n1=mid-left
	n2=right-mid
	l[n1]={}
	r[n2]={}
	for i in range(n1-1):
		l[i]=s[left+1]
	for j in range(n2-1):
		r[i]=s[mid+1]
	l[n1]=10000000
	r[n2]=10000000
	m=0
	n=0
	for k in range(left,right-1):
		c=c+1
		if l[m]<=r[m]:
			s[k]=l[m]
			m=m+1
		else:
			s[k]=r[n]
			n=n+1

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


n=int(input())
s=input().split()
for a in range(n):
	s[a]=int(s[a])
c=0
mergesort(s,s[0],s[n])
l=' '.join(s)
print(l)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int count=0;
void merge(int a[],int left,int mid,int right){
    int n1=mid-left,n2=right-mid;
    int l[n1+1],r[n2+1];
    for(int i=0;i<n1;i++){
	    l[i]=a[left+i];
	}
    for(int i=0;i<n2;i++) {
	   r[i]=a[mid+i];
	}
    l[n1]=10000000; 
    r[n2]=10000000;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        count++;
        if(l[i]<=r[j]){
            a[k]=l[i];
            i++;
        }
        else{
            a[k]=r[j];
            j++;
        }
    }
}
void mergesort(int a[],int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergesort(a,left,mid);
        mergesort(a,mid,right);
        merge(a,left,mid,right);
    }
}
 
int main(){
    int n;  
    cin>>n;
    int data[n];
    for(int i=0;i<n;i++){
        cin>>data[i];
    }
    mergesort(data,0,n);
    printf("%d",data[0]);
    for(int i=1;i<n;i++){
		 printf(" %d",data[i]);
	}  
    printf("\n%d\n",count);
    return 0;
}

Submission status: Runtime Error

Solution code:

#include<iostream>

#define MAX 10000
using namespace std;
int l[MAX / 2 + 2], r[MAX / 2 + 2];
int cnt_sum;

void merge(int a[], int left, int mid, int right) {
	int n1 = mid - left;
	int n2 = right - mid;

	for (int i = 0; i < n1; i++) {
		l[i] = a[left + i];
	}
	l[n1] = MAX;
	for (int i = 0; i < n2; i++) {
		r[i] = a[mid + i];
	}
	r[n2] = MAX;

	int p = 0, q = 0;
	for (int i = left; i < right; i++) {
		cnt_sum++;
		if (l[p] < r[q]) {
			a[i] = l[p++];
		}
		else {
			a[i] = r[q++];
		}
	}
}
void mergeSort(int a[], int left, int right) {
	if (left + 1 == right) return;
	int mid = (left + right) / 2;
	mergeSort(a, left, mid);
	mergeSort(a, mid, right);
	merge(a, left, mid, right);
}


int main(void) {

	int n;
	int s[50000];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	mergeSort(s, 0, n);

	for (int i = 0; i < n; i++) {
		cout << s[i] << " ";
	}
	cout << endl;
	cout << cnt_sum ;

	return 0;


}

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

def MergeSort(A, left, right):
    if left+1 < right:
        if (left + right) % 2 == 0:
            mid = int((left + right)/2)
        else:
            mid = int((left + right -1)/2)
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

def MergeSort(A, left, right):
    if left+1 < right:
        if (left + right) % 2 == 0:
            mid = int((left + right)/2)
        else:
            mid = int((left + right -1)/2)
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

def Merge(A, left, mid, right):
    L = [A[left + i] for i in range(mid-left)]
    R = [A[mid + i] for i in range(right-mid)]
    L.append(510000)
    R.append(510000)
    i,j = 0,0
    global cnt
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        cnt += 1

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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    L.append(510000)
    R.append(510000)
    i,j = 0,0
    global cnt
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        if L[i] > R[j]:
            A[k] = R[j]
            j += 1
        cnt += 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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

def Merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = [A[left + i] for i in range(n1)]
    R = [A[mid + i] for i in range(n2)]
    L.append(510000)
    R.append(510000)
    i,j = 0,0
    global cnt
    for k in range(left,right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        elif L[i] > R[j]:
            A[k] = R[j]
            j += 1
        cnt += 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)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime Error

Solution code:
#coding:utf-8
n = int(input())
A = list(map(int, input().split()))

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

def MergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        MergeSort(A, left, mid)
        MergeSort(A, mid, right)
        Merge(A, left, mid, right)
    
cnt = 0
MergeSort(A, 0, n)
A = " ".join([str(num) for num in A])
print(A)
print(cnt)

Submission status: Runtime 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[-1]:
        print(x, " ")
    print(s[-1])

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: Runtime Error

Solution code:
#coding: UTF-8
#mergeSort

list=[]
list_l=[]
list_r=[]
cnt=0

def mergesort(x):
	if len(x)<=1:
		return x

	mid = len(x)//2

	left=x[:mid]
	right=x[mid:]

	left=mergesort(left)
	right=mergesort(right)

	return merge(left,right)

def merge(left,right):
	merged=[]
	l_i, r_i=0, 0

	while l_i < len(left) and r_i<len(right):
		global cnt
		cnt += 1
		if left[l_i] <= right[r_i]:
			merged.append(left[l_i])
			l_i += 1
		else:
			merged.append(right[r_i])
			r_i += 1
	if l_i < len(left):
		cnt+=1
		merged.extend(left[l_i:])
	if r_i < len(right):
		cnt+=1
		merged.extend(right[r_i:])

	return merged

n=int(input())

roop=0
while(roop<n):
	list.append(int(input()))
	roop+=1

for i in list:
	print(i)

list = mergesort(list)

roop=0
while(roop<n):
	print (str(list[roop])+" ",end="")
	roop+=1
cnt+=1
print()
print(cnt)

Submission status: Runtime Error

Solution code:
#coding: UTF-8
#mergeSort

list=[]
list_l=[]
list_r=[]
cnt=0

def mergesort(x):
	if len(x)<=1:
		return x

	mid = len(x)//2

	left=x[:mid]
	right=x[mid:]

	left=mergesort(left)
	right=mergesort(right)

	return merge(left,right)

def merge(left,right):
	merged=[]
	l_i, r_i=0, 0

	while l_i < len(left) and r_i<len(right):
		global cnt
		cnt += 1
		if left[l_i] <= right[r_i]:
			merged.append(left[l_i])
			l_i += 1
		else:
			merged.append(right[r_i])
			r_i += 1
	if l_i < len(left):
		cnt+=1
		merged.extend(left[l_i:])
	if r_i < len(right):
		cnt+=1
		merged.extend(right[r_i:])

	return merged

n=int(input())

roop=0
while(roop<n):
	list.append(int(input()))
	roop+=1

list = mergesort(list)

roop=0
while(roop<n):
	print (str(list[roop])+" ",end="")
	roop+=1

cnt+=1
print()
print(cnt)

Submission status: Runtime Error

Solution code:
#coding: UTF-8
#mergeSort

list=[]
cnt=0

def mergesort(x):
	if len(x)<=1:
		return x

	mid = len(x)//2

	left=x[:mid]
	right=x[mid:]

	left=mergesort(left)
	right=mergesort(right)

	return merge(left,right)

def merge(left,right):
	merged=[]
	l_i, r_i=0, 0

	while l_i < len(left) and r_i<len(right):
		global cnt
		cnt += 1
		if left[l_i] <= right[r_i]:
			merged.append(left[l_i])
			l_i += 1
		else:
			merged.append(right[r_i])
			r_i += 1
	if l_i < len(left):
		cnt+=1
		merged.extend(left[l_i:])
	if r_i < len(right):
		cnt+=1
		merged.extend(right[r_i:])

	return merged

n=int(input())

roop=0
while(roop<n):
	list.append(int(input()))
	roop+=1

list = mergesort(list)

roop=0
while(roop<n):
	print (list[roop],end="")
	print(" ",end="")
	roop+=1
cnt+=1
print()
print(cnt)

Submission status: Runtime Error

Solution code:
def merge(a, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = a[left:left + n1] + SENTINEL
    R = a[mid:mid + n2] + SENTINEL
    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)

SENTINEL = 1000000001
n = int(input())
a = list(map(int, input().strip().split()))
count = 0
merge_sort(a, 0, len(a))
print(' '.join(map(str, a)))
print(count)

Submission status: WA: Presentation Error

Solution code:
def f(n):
    return 0 if n<2 else n+f(n/2)+f(n-n/2)
n=f(input())
print " ".join(sorted(raw_input().split(),key=int)),"\n",n

Submission status: WA: Presentation Error

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()                                                
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', cnt

Submission status: WA: Presentation Error

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()                                                
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', cnt