#include <iostream>
using namespace std;
int arr[500];
void merge(int l[],int l_len,int r[],int r_len)
{
int i=0,j=0,k=0;
while(i<l_len && j<r_len)
{
if(l[i] <= r[j])
{
arr[k++]=l[i++];
}
else arr[k++]=r[j++];
}
while(i<l_len) arr[k++]=l[i++];
while(j<r_len) arr[k++]=r[j++];
}
void merge_sort(int arr[],int len)
{
int mid = 0;
if(len<2) return;
else mid = len/2;
int l[mid+1] = {0};
int r[len-mid+1] = {0};
for(int i=0;i<mid;i++) l[i]=arr[i];
for(int i=mid;i<len;i++) l[i-mid]=arr[i];
merge_sort(l,mid);
merge_sort(r,mid);
merge(l,mid,r,len-mid);
}
int main()
{
srand(time(NULL));
int n = 50;
cout<<n<<"\n";
for(int i=0;i<n;i++)
{
arr[i] = rand()%n + 1;
cout<<arr[i]<<" ";
}
merge_sort(arr,n);
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgYXJyWzUwMF07CnZvaWQgbWVyZ2UoaW50IGxbXSxpbnQgbF9sZW4saW50IHJbXSxpbnQgcl9sZW4pCnsKCWludCBpPTAsaj0wLGs9MDsKCXdoaWxlKGk8bF9sZW4gJiYgajxyX2xlbikKCXsKCQlpZihsW2ldIDw9IHJbal0pCgkJewoJCQlhcnJbaysrXT1sW2krK107CgkJfQoJCWVsc2UgYXJyW2srK109cltqKytdOwoJfQoJd2hpbGUoaTxsX2xlbikgYXJyW2srK109bFtpKytdOwoJd2hpbGUoajxyX2xlbikgYXJyW2srK109cltqKytdOwp9CnZvaWQgbWVyZ2Vfc29ydChpbnQgYXJyW10saW50IGxlbikKewoJaW50IG1pZCA9IDA7CglpZihsZW48MikgcmV0dXJuOwoJZWxzZSBtaWQgPSBsZW4vMjsKCWludCBsW21pZCsxXSA9IHswfTsKCWludCByW2xlbi1taWQrMV0gPSB7MH07Cglmb3IoaW50IGk9MDtpPG1pZDtpKyspIGxbaV09YXJyW2ldOwoJZm9yKGludCBpPW1pZDtpPGxlbjtpKyspIGxbaS1taWRdPWFycltpXTsKCW1lcmdlX3NvcnQobCxtaWQpOwoJbWVyZ2Vfc29ydChyLG1pZCk7CgltZXJnZShsLG1pZCxyLGxlbi1taWQpOwp9CmludCBtYWluKCkKewoJc3JhbmQodGltZShOVUxMKSk7CglpbnQgbiA9IDUwOwoJY291dDw8bjw8IlxuIjsKCWZvcihpbnQgaT0wO2k8bjtpKyspIAoJewoJCWFycltpXSA9IHJhbmQoKSVuICsgMTsKCQljb3V0PDxhcnJbaV08PCIgIjsKCX0KCW1lcmdlX3NvcnQoYXJyLG4pOwoJcmV0dXJuIDA7Cn0=