Insertion sort

I reckon there is no practical use in talking once more about insertion sort, if not to have a bit of (twisted) fun. The idea of this cute sorting algorithm is that we partition our to-be-sorted collection in two blocks: the element already ordered, an the ones that still have to be processed. We check one by one the elements of the second group against the ones in the first one, till the job is done.

It should be enough to read this high level description to see that it relies on two loops proportional to the collection size, meaning that we are in the realm of the Big Oh - N Square algorithms.

On the other side it has a few advantages. First of all, it is easy to design and develop. Then we should appreciate the fact that it is an in-place algorithm (we need just one temporary element), stable and relatively efficient if the array is already near-sorted (in the best case it becomes a Big On - N algorithm).

I think that this simple C implementation should help undestanding how the algorithm works:

void insertionSort(int* vi, int len) // 1.
{
    for(int j = 1; j < len; ++j) // 2.
    {
        int temp = vi[j]; // 3.

         // 4.
        int i = j - 1; // index of last sorted value
        for(;i >= 0 && vi[i] > temp; --i)
            vi[i+1] = vi[i]; // 5.

        // 6.
        vi[i+1] = temp;
    }
}

1. It expects in input a pointer to an integer array and its size. Here is the main weakness of this implementation: it is error prone, and works just on one data type. We'll address to these issues in the next post, for the moment we just want to undestand better the algorithm.
2. External loop. We have divided the array in two parts. On the left we have just one element - that we call "sorted" - on the right we have all the other one - that we assume "unsorted".
3. We consider the first element of the "unsorted" subarray. We are duplicating it in a temporary variable, so that we can reuse its location in the array, if we need to move the "sorted" elements.
4. Inner loop. We scan backward the "sorted" elements until we see that the current "sorted" element is less than the currently checked "unsorted" one. Naturally we pay attention to stop when we get at the beginning of the array.
5. We are making room for the "unsorted" element, moving all the "sorted" elements bigger than it one step to the right.
6. We have made room for "temp" in the "sorted" area at position "i+1". We put it there.

Running the code step by step in debug mode should help a lot undestanding better how things work.