Insertion Sort

Idea

Start with an empty left hand and cards face down.
Remove one card at a time from the pile of cards and find the correct position for this card.
To find the position for the card, you need to compare this card with the cards in your hand from right to left.
At all times the cards held in the left hand are sorted.

Input:
Sequence of numbers $(a1, a2, .... aN)$.

Output:
A permutation reordering $( a'1, a'2, .... a'N)$ such that $a'1 <= a'2 <= .... <= a'N$

Loop Invariant

After every iteration you should have two parts of the array
    1st part will have sorted elements
    2nd part will have unsorted elements.

Pseudo code

INSERTION-SORT (A)
    for j = 2 to A.length
        i = j - 1
        key = A[j]
        while A[i] > key and i > 0
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key

NOTE: It is not important to name the array indexes with just i and j.
Look how nicely the concept of how i and j are fitting in. Even though j is used with the outer loop - what it is suggesting is that the index value of j tries and manipulates on the right side of the array. and for variable i, it manipulates the left side of the array

NOTE: Condition while A[i] > key and i > 0 is using 1-based indexing¹

Verifying Loop Invariant

Initialization

First loop iteration, when $J$ is 2. The subarray $A[1...J-1]$ consists of only single element $A[1]$ which is the original element. This subarray is trivially sorted.

Maintenance

We need to show each iteration maintains loop invariant.
During each iteration, J is from 2 -> A.length to the right till max number of elements in the array. Which means J = 2, then A[2] is picked up and placed in the left subarray. The inner while loop takes care of placing the element A[2] in the proper order within subarray A[1..2].

Termination

When the loop terminates we have J > A.length. Because each iteration increases J by 1, we would have J as A.length+1. Using this condition on the loop invariant, we have the sorted array of size A[1...J] ie A[1...N] which is the size of the original input array. So we can conclude that the entire array is sorted and that the algorithm is correct.

Code

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;

       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

// Poor implementation usage
void insertion_sort(int *arr, int len) {
    int i=1,j,n=len;
    for(int i = 1; i < n; i++) { //Issue: Poor clarity on index usage
        j = i;
        int v = arr[j--];    //Issue with j--
        while (j>=0 && v < arr[j]) { 
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = v;
    }
}

Big-O Analysis

The outer loop with I moves from 1 to N and the inner loop with move from N-1 to 1.

1 * N-1 + 2 * N-2 + 3 * N-3 + .... + N/2 * N/2 + .... + N-1 * 1 = Summation k from 1 to N-1 [ k * (N-k) ]

I don't know which series is this?

How many CPU cycles would it take to calculate the above: Worst case would be O(N^2)

¹. 1-based indexing with Insertion Sort Pseudocode ↩