#include <iostream>
using namespace std;
void merge(int a[],int left[],int right[])
{
int nl=sizeof(left)/sizeof(left[0]);
int nr=sizeof(right)/sizeof(right[0]);
int i=0,j=0,k=0;
while((i<=nl)&&(j<=nr))
{
if(left[i]<=right[j])
a[k++]=left[i++];
else
a[k++]=right[j++];
}
while(i<=nl)
a[k++]=left[i++];
while(j<=nr)
a[k++]=right[i++];
}
void mergesort(int a[])
{
int n=sizeof(a)/sizeof(a[0]);
if(n<2)return;
int mid=n/2;
int left[mid+1],right[n-mid+1];
for(int i=0;i<mid;i++)left[i]=a[i];
for(int j=mid;j<n;j++)right[j-mid]=a[j];
mergesort(left);
mergesort(right);
merge(a,left,right);
}
int main() {
// your code goes here
int a[]={6,8,9,1,2};
mergesort(a);
for(int i=0;i<5;++i)cout<<a[i]<<" ";
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2b2lkIG1lcmdlKGludCBhW10saW50IGxlZnRbXSxpbnQgcmlnaHRbXSkKewoJaW50IG5sPXNpemVvZihsZWZ0KS9zaXplb2YobGVmdFswXSk7CglpbnQgbnI9c2l6ZW9mKHJpZ2h0KS9zaXplb2YocmlnaHRbMF0pOwoJaW50IGk9MCxqPTAsaz0wOwoJd2hpbGUoKGk8PW5sKSYmKGo8PW5yKSkKCXsKCQlpZihsZWZ0W2ldPD1yaWdodFtqXSkKCQlhW2srK109bGVmdFtpKytdOwoJCWVsc2UKCQlhW2srK109cmlnaHRbaisrXTsKCX0KCXdoaWxlKGk8PW5sKQoJYVtrKytdPWxlZnRbaSsrXTsKCXdoaWxlKGo8PW5yKQoJYVtrKytdPXJpZ2h0W2krK107Cn0Kdm9pZCBtZXJnZXNvcnQoaW50IGFbXSkKewoJaW50IG49c2l6ZW9mKGEpL3NpemVvZihhWzBdKTsKCWlmKG48MilyZXR1cm47CglpbnQgbWlkPW4vMjsKCWludCBsZWZ0W21pZCsxXSxyaWdodFtuLW1pZCsxXTsKCWZvcihpbnQgaT0wO2k8bWlkO2krKylsZWZ0W2ldPWFbaV07Cglmb3IoaW50IGo9bWlkO2o8bjtqKyspcmlnaHRbai1taWRdPWFbal07CgltZXJnZXNvcnQobGVmdCk7CgltZXJnZXNvcnQocmlnaHQpOwoJbWVyZ2UoYSxsZWZ0LHJpZ2h0KTsKfQppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCSBpbnQgYVtdPXs2LDgsOSwxLDJ9OwoJIG1lcmdlc29ydChhKTsKCSBmb3IoaW50IGk9MDtpPDU7KytpKWNvdXQ8PGFbaV08PCIgIjsKCXJldHVybiAwOwp9