#include<bits/stdc++.h>
using namespace std;
void merge(int arr[],int l,int mid,int r){
int n1= mid-l+1;
int n2= r-mid;
//temp arrays
int a[n1];
int b[n2];
//array ke elements ko 2 temp arrays mein bhar rhe hai
for (int i = 0; i < n1; i++)
{
a[i]=arr[l+i];
}
for (int i = 0; i < n2; i++)
{
b[i]=arr[mid+1+i];
}
//checing when putting the values backing in the k array
int i=0;
int j=0;
int k=l;
while(i<n1 && j<n2){
if(a[i]<b[j]){
arr[k]=a[i];
k++;
i++;
}
else{
arr[k]=b[j];
k++;
j++;
}
}
// for the last one
while(i<n1){
arr[k]=a[i];
k++;
i++;
}
while(j<n2){
arr[k]=b[j];
k++;
j++;
}
}
void mergeSort(int arr[],int l,int r){
if(l<r){
int mid=(l+r)/2;
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}
}
int main(){
int arr[]={5,4,3,2,1};
mergeSort(arr,0,4);
for (int i = 0; i < 5; i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
CiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIG1lcmdlKGludCBhcnJbXSxpbnQgbCxpbnQgbWlkLGludCByKXsKICAgIGludCBuMT0gbWlkLWwrMTsKICAgIGludCBuMj0gci1taWQ7CiAgICAKICAgIC8vdGVtcCBhcnJheXMKICAgIGludCBhW24xXTsKICAgIGludCBiW24yXTsKCiAgICAvL2FycmF5IGtlIGVsZW1lbnRzIGtvIDIgdGVtcCBhcnJheXMgbWVpbiBiaGFyIHJoZSBoYWkKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjE7IGkrKykKICAgIHsKICAgICAgICBhW2ldPWFycltsK2ldOwoKICAgIH0KICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjI7IGkrKykKICAgIHsKICAgICAgICBiW2ldPWFyclttaWQrMStpXTsKICAgICAgICAKICAgIH0KCiAgICAvL2NoZWNpbmcgd2hlbiBwdXR0aW5nIHRoZSB2YWx1ZXMgYmFja2luZyBpbiB0aGUgayBhcnJheQogICAgaW50IGk9MDsKICAgIGludCBqPTA7CiAgICBpbnQgaz1sOwogICAgd2hpbGUoaTxuMSAmJiBqPG4yKXsKICAgICAgICBpZihhW2ldPGJbal0pewogICAgICAgICAgICBhcnJba109YVtpXTsKICAgICAgICAgICAgaysrOwogICAgICAgICAgICBpKys7CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIGFycltrXT1iW2pdOwogICAgICAgICAgICBrKys7CiAgICAgICAgICAgIGorKzsKICAgICAgICB9CiAgICB9CgogICAgLy8gZm9yIHRoZSBsYXN0IG9uZQogICAgd2hpbGUoaTxuMSl7CiAgICAgICAgYXJyW2tdPWFbaV07CiAgICAgICAgaysrOwogICAgICAgIGkrKzsKICAgIH0KICAgIHdoaWxlKGo8bjIpewogICAgICAgIGFycltrXT1iW2pdOwogICAgICAgIGsrKzsKICAgICAgICBqKys7CiAgICB9ICAgIAp9Cgp2b2lkIG1lcmdlU29ydChpbnQgYXJyW10saW50IGwsaW50IHIpewogICAgaWYobDxyKXsKICAgICAgICBpbnQgbWlkPShsK3IpLzI7CiAgICAgICAgbWVyZ2VTb3J0KGFycixsLG1pZCk7CiAgICAgICAgbWVyZ2VTb3J0KGFycixtaWQrMSxyKTsKICAgICAgICBtZXJnZShhcnIsbCxtaWQscik7CiAgICB9Cn0KCmludCBtYWluKCl7CiAgICBpbnQgYXJyW109ezUsNCwzLDIsMX07CiAgICBtZXJnZVNvcnQoYXJyLDAsNCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IDU7IGkrKykKICAgIHsKICAgICAgICBjb3V0PDxhcnJbaV08PCIgIjsKICAgIH0KICAgIGNvdXQ8PGVuZGw7CiAgICByZXR1cm4gMDsKfQ==