#include <iostream>
#include <ctime>
using namespace std;
int srav=0,pris=0;
void merge(int a[], int l, int mind, int r) {
int i, j, k;
int n1=mind-l+1;
int n2=r-mind;
int L[n1], R[n2];
for (i=0;i<n1;i++) {
L[i]=a[l+i];
++pris;
}
for (j=0;j<n2;j++) {
R[j]=a[mind+1+j];
++pris;
}
i=0;
j=0;
k=l;
while (i<n1&&j<n2) {
++srav;
if (L[i]<=R[j]) {
a[k]=L[i];
++pris;
++i;
}
else {
a[k]=R[j];
++pris;
++j;
}
++k;
}
while (i<n1) {
a[k]=L[i];
++srav;
i++;
k++;
}
while (j<n2) {
a[k]=R[j];
++pris;
j++;
k++;
}
return;
}
void merge_sort(int a[], int l, int r) {
if (l<r) {
int mid=l+(r-l)/2;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
merge(a,l,mid,r);
}
return;
}
int main() {
int n,f=0,sumpris=0,sumsrav=0,i=0;
cin>>n;
srand(time(NULL));
int a[n];
for (f=0;f<7;++f) {
i=0;
srav=0;
pris=0;
while (i<n) {
a[i]=rand()%150;
++i;
}
merge_sort(a,0,n-1);
sumsrav+=srav;
sumpris+=pris;
cout<<"сравнений="<<srav<<" "<<"присваиваний="<<pris<<endl;
}
cout<<"среднее сравнений="<<sumsrav/7<<" "<<"среднее присваиваний="<<sumpris/7;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3RpbWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgc3Jhdj0wLHByaXM9MDsKCnZvaWQgbWVyZ2UoaW50IGFbXSwgaW50IGwsIGludCBtaW5kLCBpbnQgcikgewogICAgaW50IGksIGosIGs7CiAgICBpbnQgbjE9bWluZC1sKzE7CiAgICBpbnQgbjI9ci1taW5kOwogICAgaW50IExbbjFdLCBSW24yXTsKICAgIGZvciAoaT0wO2k8bjE7aSsrKSB7CiAgICAgICAgTFtpXT1hW2wraV07CiAgICAgICAgKytwcmlzOwogICAgfQogICAgZm9yIChqPTA7ajxuMjtqKyspIHsKICAgICAgICBSW2pdPWFbbWluZCsxK2pdOwogICAgICAgICsrcHJpczsKICAgIH0KICAgIGk9MDsKICAgIGo9MDsKICAgIGs9bDsKICAgIHdoaWxlIChpPG4xJiZqPG4yKSB7CiAgICAgICAgKytzcmF2OwogICAgICAgIGlmIChMW2ldPD1SW2pdKSB7CiAgICAgICAgICAgIGFba109TFtpXTsKICAgICAgICAgICAgKytwcmlzOwogICAgICAgICAgICArK2k7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBhW2tdPVJbal07CiAgICAgICAgICAgICsrcHJpczsKICAgICAgICAgICAgKytqOwogICAgICAgIH0KICAgICAgICArK2s7CiAgICB9CiAgICB3aGlsZSAoaTxuMSkgewogICAgICAgIGFba109TFtpXTsKICAgICAgICArK3NyYXY7CiAgICAgICAgaSsrOwogICAgICAgIGsrKzsKICAgIH0KICAgIHdoaWxlIChqPG4yKSB7CiAgICAgICAgYVtrXT1SW2pdOwogICAgICAgICsrcHJpczsKICAgICAgICBqKys7CiAgICAgICAgaysrOwogICAgfQogICAgcmV0dXJuOwp9Cgp2b2lkIG1lcmdlX3NvcnQoaW50IGFbXSwgaW50IGwsIGludCByKSB7CiAgICBpZiAobDxyKSB7CiAgICBpbnQgbWlkPWwrKHItbCkvMjsKICAgIG1lcmdlX3NvcnQoYSxsLG1pZCk7CiAgICBtZXJnZV9zb3J0KGEsbWlkKzEscik7CiAgICBtZXJnZShhLGwsbWlkLHIpOwp9CnJldHVybjsKfQoKaW50IG1haW4oKSB7CglpbnQgbixmPTAsc3VtcHJpcz0wLHN1bXNyYXY9MCxpPTA7CgljaW4+Pm47CglzcmFuZCh0aW1lKE5VTEwpKTsKCWludCBhW25dOwoJZm9yIChmPTA7Zjw3OysrZikgewoJaT0wOwoJc3Jhdj0wOwoJcHJpcz0wOwoJd2hpbGUgKGk8bikgewoJCWFbaV09cmFuZCgpJTE1MDsKCQkrK2k7Cgl9CgltZXJnZV9zb3J0KGEsMCxuLTEpOwoJc3Vtc3Jhdis9c3JhdjsKCXN1bXByaXMrPXByaXM7CiAgICBjb3V0PDwi0YHRgNCw0LLQvdC10L3QuNC5PSI8PHNyYXY8PCIgIjw8ItC/0YDQuNGB0LLQsNC40LLQsNC90LjQuT0iPDxwcmlzPDxlbmRsOwoJfQoJY291dDw8ItGB0YDQtdC00L3QtdC1INGB0YDQsNCy0L3QtdC90LjQuT0iPDxzdW1zcmF2Lzc8PCIgIjw8ItGB0YDQtdC00L3QtdC1INC/0YDQuNGB0LLQsNC40LLQsNC90LjQuT0iPDxzdW1wcmlzLzc7CglyZXR1cm4gMDsKfQ==