Sample C source code for the insertion sort.

/* With each pass, first element in unsorted
sublist is inserted into sorted sublist.
*/
void insertionSort(int list[], int n)
{
   int cur, located, temp, j;
   for (cur = 1; cur <= n ; cur++){
     located = 0;
     temp = list[cur];
     for ( j = cur - 1; j >= 0 && !located;)
        if(temp < list[ j ]){
           list[j + 1]= list[ j ];
           j--;
        }
        else
           located = 1;
     list[j + 1] = temp;
   }
   return;
}

The best case is when the data are already in order. Only one comparison is made for each position, so the comparison complexity is O(n), and the data movement is 2n – 1 , i.e. it is O(n).

The worst case is when the data are in reverse order. Each data element is to be moved to new position and for that each of the other elements have to be shifted. This works out to be complexity of .