How to sort an array using recursion in C++

In this post, we will learn how to sort an array using recursion in C++ programming. An array is a continuous memory block in which elements can be extracted sequentially. for example a[]=5 3 2 4 1
input:

n=5
before sorting:5 3 2 4 1

output:

after sorting:1 2 3 4 5

Sorting an array using recursion in C++

Lets consider a situation where we have sorted elements up to (n-2)th index,then we have given array a[] as 2 3 4 5 1. the last element needs to get inserted in its actual position for complete sorting of given array as 1 2 3 4 5.
So we will create recursive function for sorting and inserting the elements.
In sort function,if number of elements in array will be 0 or 1 then we will return the array. For each recursive call, last element will be inserted to its actual position.

void sorting(vector<int>&v)
{
   if(v.size()<=1)
   return;
   int temp=v[v.size()-1];
   v.pop_back();
   sorting(v);
   insertion(v,temp);
}

insertion function:

void insertion(vector<int>&v,int temp)
{
   if(v.size()==0 || v[v.size()-1]<=temp)
   {
   v.push_back(temp);
   return;
   }
   int x=v[v.size()-1];
   v.pop_back();
   insertion(v,temp);
   v.push_back(x);
   
}

Code for sorting the array using recursion:

#include <bits/stdc++.h>
using namespace std;
void insertion(vector<int>&v,int temp)
{
   if(v.size()==0 || v[v.size()-1]<=temp)
   {
   v.push_back(temp);
   return;
   }
   int x=v[v.size()-1];
   v.pop_back();
   insertion(v,temp);
   v.push_back(x);
}
void sorting(vector<int>&v)
{
   if(v.size()<=1)
   return;
   int temp=v[v.size()-1];
   v.pop_back();
   sorting(v);
   insertion(v,temp);
}
int main()
{
    vector<int>v={5,3,2,4,1};
    sorting(v);
   for(auto it:v)
   cout<<it<<" ";
    return 0;
}

input: 5 3 2 4 1
output: 1 2 3 4 5

From the output, you can see that we have successfully completed our task by sorting the array.