recursive-sorting

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define inf 2e18
int MOD=1000000007;//998244353;
const int nn=1000050;
bool prime[nn];    //array to store precalculated primes till 10^6
void cal_primes(){memset(prime,true,sizeof(prime)); for(int i=2;i<=sqrt(nn);++i){ if(prime[i]==true){ for(int j=i*i;j<=nn;j+=i){prime[j]=false;}}}}

void shift(vector<int>& arr,int n)
{
    int l=arr[n-1],pos=(n-2);
    //this while loop, keeps on moving/shifting elements to one place towards the right,
    //until the correct position for the last element is found. Then inserts into that place.
    //can be done with repeated swapping too.
    while(pos>=0 && arr[pos]>l)
    {
        arr[pos+1]=arr[pos];
        pos--;
    }
    arr[pos+1]=l;
}

void recbsort(vector<int>& arr,int n)
{
    //base case: 1 element, we don't need to do anything
    if(n<=1)
        return;

    //this loop, puts the largest element of current considered array in the last position.
    //so basically, it sorts from back, that is puts, largest elements in their proper place
    //for the current array/subarray
    for(int i=0;i<n-1;i++)
    {
        int temp;
        if(arr[i+1]<arr[i])
        {
            temp=arr[i];
            arr[i]=arr[i+1];
            arr[i+1]=temp;
        }
    }

    recbsort(arr,n-1);
}

void recsort(vector<int>& arr, int n)
{
    //base case: 1 element, we don't need to do anything
    if(n<=1)
        return;

    recsort(arr,n-1);
    shift(arr,n);   //insert the lase element in its correct position
}

void solve(int t)
{
    int testcases=t;
    while(t--)
    {
        int n;cin>>n;
        vector<int>arr(n);
        for(int i=0;i<n;i++)
            cin>>arr[i];

        cout<<"initial array: ";
        for(auto it:arr)
            cout<<it<<" ";
        cout<<endl;

        recsort(arr,n);     //recursive insertion sort
        recbsort(arr,n);    //recursive bubble sort

        cout<<"sorted array: ";
        for(auto it:arr)
            cout<<it<<" ";
    }
}

main()
{
    auto start=chrono::system_clock::now();
    {
        ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        int t=1;
    //  cin>>t;
        solve(t);
    }
    auto end=chrono::system_clock::now();
    chrono::duration<double> elapsed=end-start;
//  cout<<endl<<"Time taken: "<<elapsed.count()<<" sec";
    return 0;
}