/*A lecture on recursion and sorting
 *Programeer: Ali Sabbir.
 */
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
int pos(int*, int,int, const int);
void insert(int*,int,int);
int main(){
	const int size =10;
	int A[size];
	srand(time(0));
	for(int i=0;i<size;i++) A[i]=rand()%size;
	for(i=1;i<size;++i)insert(A,i,pos(A,0,i-1,i));
	for(i=0;i<size;++i) cout<<A[i]<<" ";
	
    return 0;
}
void insert(int *A, int source, int destination){
	int temp=A[source];
	for(int i=source;i>destination;--i)A[i]=A[i-1];
	A[i]=temp;
}

int pos(int *A,int first,int last,const int key_index){
	int mid = (first+last)/2;
	if(first>last) return first;
	else if(A[key_index]>=A[mid])pos(A,mid+1,last,key_index);
	else if(A[key_index]<A[mid]) pos(A,first,mid-1,key_index);
}