Insertion sort algorithm

The insertion sort algorithm works as follows.

• We start with second element of the array, considering the first element of the array as a sub-array, which is already sorted.
• Then we are looking for the right position of the current element (the second one) in the sub-array in such a way to keep the sub-array sorted.
• Free the position found by moving all elements from the right position till the position of the current element down and put the current element in the right place.
• Consider the third element and find the right position in the sub-array containing now the first and the second elements. Then put ...
• Keep doing this until the sorted sub-array contains all elements of the original array.

Although it is easier to explain the idea of the insertion sort in two consecutive steps - first, find the right position, and second, insert the current element into the right position moving all elements starting from this position down, it is much more efficient to implement these two steps together in one loop. Lets compare two functions:

void isort(int data[], int N) { int i, j, k, s; for(i=1;i<N;i++){ s = data[i]; // find the right spot for the element s for(j=i-1;j>=0 && data[j]>s;j--); // now j+1 is the index of the position where s should be // move all elements [j+1, i-1] down for(k=i;k>j+1;k--) data[k] = data[k-1]; // put s in the right spot if( j < i-1 ) data[j+1] = s; } }

void isort(int data[], int N) { int i, j, s; for(i=1;i<N;i++){ s = data[i]; // start moving all elements greater than s down for(j=i-1; j>=0 && data[j]>s; j--) data[j+1] = data[j]; // put s in the right spot if( j < i-1 ) data[j+1] = s; } }

Below you can see the table that shows how runtime (in milliseconds) of these versions differ.