3.1 insertion_sort

Here is the insertion sort algorithm in three variants. We will discuss various points about algorithm design and analysis using these three versions.

Let C_IS(n) be the number of sequence entry comparisons needed to perform insertion sort in the worst case over all input sequences of size n.
Let C_I(n) be the worst case number of comparisons to insert a number into a sorted list of n numbers.

Nested loops version:

void insertion_sort(sequence A) {
  // Let n = size(A).  Elements A[1..n] are permuted into nondecreasing order. 
1    for (int i = 2; i <= n; ++i)
        // Invariant: A[1..i-1] is sorted. 
        // Now bubble A[i] down to it's proper location, making A[1..i] sorted. 
2       for (int j = i; j > 1; --j)
3          if (A[j] < A[j-1])
4             swap(A[j], A[j-1]);
  }

Separation of concerns version.

#include "insert.h"

   
void insertion_sort( sequence A ) {
  // Let n = size(A).  Elements A[1..n] are permuted into nondecreasing order. 
1    for (int i = 2; i <= n; ++i)
        // Invariant: A[1..i-1] is sorted. 
2       insert(A, i); // we explain this function where it is defined. 
     }
  }

Fully recursive version (giant step, baby step)

#include "insert.h"

   
void insertion_sort(sequence A){
  // Let n = size(A). Elements A[1..n] are permuted into nondecreasing order. 
1    if (n > 1) {
2       insertion_sort(A, n-1);
3       insert(A, n);
     }
  }

Evidently C_IS(n) = C_IS(n-1) + C_I(n-1).