#include <stdio.h>
#include <stdlib.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void MergeSort();
void Merging();
int main(){
int arr[100];
int i;
for(i=0;i<5;i++){
}
for(i=0;i<5;i++){
}
MergeSort(arr,0,4);
for(i=0;i<5;i++){
}
return 0;
}
void MergeSort(int arr[],int l,int h){
if(l<h){
int mid = (l+h)/2;
MergeSort(arr,l,mid);
MergeSort(arr,mid+1,h);
Merging(arr,l,mid,h);
}
}
void Merging(int arr[], int l, int mid, int h){
int i1 = l,i2 = mid+1, j1 = mid, j2 = h;
int b[6];
int k=l;
while(i1<=j1&&i2<=j2){
if(arr[i1]<arr[i2]){
b[k++] = arr[i1++];
}else{
b[k++] = arr[i2++];
}
}
while(i1<=j1){
b[k++] = arr[i1++];
}
while(i2<=j2){
b[k++] = arr[i2++];
}
int i;
for(i=l;i<=h;i++){
arr[i] = b[i];
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCi8qIHJ1biB0aGlzIHByb2dyYW0gdXNpbmcgdGhlIGNvbnNvbGUgcGF1c2VyIG9yIGFkZCB5b3VyIG93biBnZXRjaCwgc3lzdGVtKCJwYXVzZSIpIG9yIGlucHV0IGxvb3AgKi8Kdm9pZCBNZXJnZVNvcnQoKTsKdm9pZCBNZXJnaW5nKCk7CgppbnQgbWFpbigpewogICAgaW50IGFyclsxMDBdOwogICAgaW50IGk7CiAgICBmb3IoaT0wO2k8NTtpKyspewogICAgICAgIHNjYW5mKCIlZCIsJmFycltpXSk7CiAgICB9CiAgICBwcmludGYoIlVuc29ydGVkXG4iKTsKICAgIGZvcihpPTA7aTw1O2krKyl7CiAgICAgICAgcHJpbnRmKCIlZCAiLGFycltpXSk7CiAgICB9CiAgICBwcmludGYoIlxuIik7CiAgICAKICAgIE1lcmdlU29ydChhcnIsMCw0KTsKICAgIAogICAgcHJpbnRmKCJTb3J0ZWRcbiIpOwogICAgZm9yKGk9MDtpPDU7aSsrKXsKICAgICAgICBwcmludGYoIiVkICIsYXJyW2ldKTsKICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0Kdm9pZCBNZXJnZVNvcnQoaW50IGFycltdLGludCBsLGludCBoKXsKICAgIGlmKGw8aCl7CiAgICAgICAgaW50IG1pZCA9IChsK2gpLzI7CiAgICAgICAgTWVyZ2VTb3J0KGFycixsLG1pZCk7CiAgICAgICAgTWVyZ2VTb3J0KGFycixtaWQrMSxoKTsKICAgICAgICBNZXJnaW5nKGFycixsLG1pZCxoKTsKICAgIH0KfQp2b2lkIE1lcmdpbmcoaW50IGFycltdLCBpbnQgbCwgaW50IG1pZCwgaW50IGgpewogICAgaW50IGkxID0gbCxpMiA9IG1pZCsxLCBqMSA9IG1pZCwgajIgPSBoOwogICAgaW50IGJbNl07CiAgICBpbnQgaz1sOwogICAgd2hpbGUoaTE8PWoxJiZpMjw9ajIpewogICAgICAgIGlmKGFycltpMV08YXJyW2kyXSl7CiAgICAgICAgICAgIGJbaysrXSA9IGFycltpMSsrXTsKICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgYltrKytdID0gYXJyW2kyKytdOwogICAgICAgIH0KICAgIH0KICAgIHdoaWxlKGkxPD1qMSl7CiAgICAgICAgYltrKytdID0gYXJyW2kxKytdOwogICAgfQogICAgd2hpbGUoaTI8PWoyKXsKICAgICAgICBiW2srK10gPSBhcnJbaTIrK107CiAgICB9CiAgICBpbnQgaTsKICAgIGZvcihpPWw7aTw9aDtpKyspewogICAgICAgIGFycltpXSA9IGJbaV07CiAgICB9Cn0=