Recursive-InsertionSort.cs

void InsertionSort(int [] A, int n)
{
	int curr = A[n];
	if (n != 0)
		InsertionSort(A, (n-1));
	PushIntoItsSpot(A, curr, (n-1));
}
void PushIntoItsSpot(int [] A, int val, int rpos)
{
	while(rpos >= 0 && A[rpos] > val)
		A[rpos+1] = A[rpos--];
	A[++rpos] = val;
}
void Main()
{
	var A = new int [] {4, 1, -1, 12, 5};
	Console.WriteLine(A);
	InsertionSort(A, A.Length-1);
	Console.WriteLine(A);
}