// MergeSort
#include <iostream>
using namespace std;
void Merge(int *a,int *x,int *y,int s,int e){
int i=s;
int mid = (s+e)/2;
int j=mid+1;
int k=s;
while(i<=mid && j<=e){
if(x[i]<y[j]){
a[k++]=x[i++];
}
else{
a[k++]=y[j++];
}
}
while(i<=mid){
a[k++]=x[i++];
}
while(j<=e){
a[k++]=y[j++];
}
}
void MergeSort(int *a,int s,int e){
if(s>=e){
return;
}
// Divide
int x[100],y[100];
int mid = (s+e)/2;
for(int i=s;i<=mid;i++){
x[i]=a[i];
}
for(int i=mid+1;i<=e;i++){
y[i]=a[i];
}
// Sort
MergeSort(x,s,mid);
MergeSort(y,mid+1,e);
// Merge
Merge(a,x,y,s,e);
}
int main(){
int a[]={6,5,4,3,2,1};
int n=sizeof(a)/sizeof(int);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
MergeSort(a,0,n-1);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
Ly8gTWVyZ2VTb3J0CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgTWVyZ2UoaW50ICphLGludCAqeCxpbnQgKnksaW50IHMsaW50IGUpewoJaW50IGk9czsKCWludCBtaWQgPSAocytlKS8yOwoJaW50IGo9bWlkKzE7CglpbnQgaz1zOwoJd2hpbGUoaTw9bWlkICYmIGo8PWUpewoJCWlmKHhbaV08eVtqXSl7CgkJCWFbaysrXT14W2krK107CgkJfQoJCWVsc2V7CgkJCWFbaysrXT15W2orK107CgkJfQoJfQoJd2hpbGUoaTw9bWlkKXsKCQlhW2srK109eFtpKytdOwoJfQoJd2hpbGUoajw9ZSl7CgkJYVtrKytdPXlbaisrXTsKCX0KfQoKdm9pZCBNZXJnZVNvcnQoaW50ICphLGludCBzLGludCBlKXsKCWlmKHM+PWUpewoJCXJldHVybjsKCX0KCS8vIERpdmlkZQoJaW50IHhbMTAwXSx5WzEwMF07CglpbnQgbWlkID0gKHMrZSkvMjsKCWZvcihpbnQgaT1zO2k8PW1pZDtpKyspewoJCXhbaV09YVtpXTsKCX0KCglmb3IoaW50IGk9bWlkKzE7aTw9ZTtpKyspewoJCXlbaV09YVtpXTsKCX0KCS8vIFNvcnQKCU1lcmdlU29ydCh4LHMsbWlkKTsKCU1lcmdlU29ydCh5LG1pZCsxLGUpOwoJLy8gTWVyZ2UKCU1lcmdlKGEseCx5LHMsZSk7Cn0KCmludCBtYWluKCl7CglpbnQgYVtdPXs2LDUsNCwzLDIsMX07CglpbnQgbj1zaXplb2YoYSkvc2l6ZW9mKGludCk7CgoJZm9yKGludCBpPTA7aTxuO2krKyl7CgkJY291dDw8YVtpXTw8IiAiOwoJfQoJY291dDw8ZW5kbDsKCU1lcmdlU29ydChhLDAsbi0xKTsKCWZvcihpbnQgaT0wO2k8bjtpKyspewoJCWNvdXQ8PGFbaV08PCIgIjsKCX0KCWNvdXQ8PGVuZGw7CgoJcmV0dXJuIDA7Cn0=