# 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.