Implementing Insertion sort in C/C++

Below function implements the insertion sort algorithm. The function takes input as a array of integers and size of the array.
The sorting is performed in place. 


void InsertionSort(int * array, int size)
{
    //we are starting from second element of the array
    for(int counter = 1; counter < size; counter++)
    {
        int nKey = array[counter];
        int tempCounter = counter-1;
        while(tempCounter >= 0 && array[tempCounter] > nKey )
        {           
            array[tempCounter+1] = array[tempCounter];
            tempCounter--;
        }
        array[tempCounter+1] = nKey;       
    }
}

Finding Middle node of the singly link list with recursion

You could find middle of the single linked list in multiple ways :

1. Simple traverse whole list once to count number of nodes in the list, then again traverse till mid element.
2. Use two list pointers, in one pass increment first list pointer by two nodes and second list pointer by one node, this way when first list pointer will reach to end of list our second pointer will be pointing to the middle of the list.
3. Use recursion to find mid.

Here we will discuss how  to reach till the mid using recursion:

To find mid you will require two things, one number elements and second how many elements we have traversed. This can be achieved using two variables one will keep track of at which element we are and one will count number of nodes till end.

int FindMid(Node * head, int nNumberOfNode = 0)

{

      if( NULL == head )

      {

            return 0;

      }

      ++ nNumberOfNode;

      int nNodeBackTraverced = FindMid(head->next, nNumberOfNode);

      if( (nNodeBackTraverced == (nNumberOfNode - 1)) || (nNodeBackTraverced  == nNumberOfNode) )

            cout << "Mid Node data: " << head->data << endl;

      return ++nNodeBackTraverced;

}

The or condition in the if will take care of both, Odd number of nodes as well as even number of nodes.