Insertion sort

It's a simple sorting algorithm that, even if asymptotically expensive, O(N**2), it results to be cheap for small data set.

Its idea is comparing each element starting from the second up to the last one with its predecessor. While we found smaller items on its left, move those ones to the right, to make room to it.

Here is my C++ implementation:

void insertionSort(std::vector<int>& data)
{
    for(unsigned i = 1; i < data.size(); ++i) // 1
    {
        int value = data[i]; // 2
        int j = i - 1; // 3
        while(j >= 0 && data[j] > value)
        {
            data[j+1] = data[j]; // 4
            --j;
        }
        data[j+1] = value; // 5
    }
}

1. Loop on all the elements after the first one.
2. Cache the current element.
3. Loop backward on the elements on the left of the current one until we found something smaller, or there is nothing more to check.
4. Make room to the current element.
5. Place the element in order.

Full code is on github. As bonus you will find there also a basic GoogleTest test.