#include <iostream>
using namespace std;
void ordonare_recursiva(int a[],int n){
//daca am terminat de sortat, terminam recusivitatea
int x,j;
if(n<1){
return;
}
//sorta recursiv n-1 elemente
ordonare_recursiva(a,n-1);
//notam cu x elementul pe care vrem sa-l introducem in sir
x=a[n-1];
//includem an n-lea element in sir
//pornim de la coada sirului s
//si vedem fata de cine este mai mic. Cat timp este mai mic
//continuam sa trecem prin sirul de n-1 termeni cand gasim un termen
//mai mic decat el, atunci ne oprim. Am sortat coada sirului
//in apelul recursiv putem considera un element mai putin
//penultimul element
j=n-2;
//cat timp x mai mic decat termenii
//si nu am ajuns la primul termen
while(j>=0&&a[j]>x){
//mutam sirul la
a[j+1]=a[j];
j--;
}
//acum introducem valoarea x
a[j+1]=x;
}
int main(){
int n,a[1000],i;
cout<<"Introduceti numarul de termeni:";
cin>>n;
cout<<"Introduceti termenii:\n";
for(i=0;i<n;i++){
cin>>a[i];
}
ordonare_recursiva(a,n);
cout<<"Termenii ordonati crescator:\n";
for(i=0;i<n;i++){
cout<<a[i]<<" ";
}
return 0;
}
