3.2 insert

Problem Insert(sequence A, n)

• Input: sequence A has at least n elements, and A[1..n-1] are in nondecreasing order.
• Output: A[1..n] is permuted into nondecreasing order. In other words, A[n] is inserted in the appropriate place among the preceeding n-1 sorted values.

This first version of insert is equivalent to the inner loop of the first insertion sort algorithm we discussed, but it's recursive expression saves having to invent a loop invariant. When optimization level -O4 is set on a C++ compiler there will be no call stack overhead for the recursion (tail recursion).

  inline void insert(sequence A, int n) { // solves Insert problem
1    if ( n > 1 and A[n] < A[n-1] ) {// otherwise, A[1..n] is already sorted. 
2       swap(A[n-1], A[n]);
        // now largest item is at A[n] and A[1..n-1] meets input requirements of insert problem. 
3       insert(A, n-1);
        // now A[1..n] is sorted. 
     }
  }

Various practical optimizations are possible, for instance this more efficient data movement.

  void insert(sequence A, int n) {
    // first find location where A[n] should be inserted. 
1   for (int j = n-1; j > 0 and A[j] > A[n]; j--) ;
2   ++j;
   // Now j indexes the first entry greater than A[n],
   // so shift A[j..n-1] up by one and put A[n] at j-th position. 
3   if (j < n) {
4      number tmp = A[n];
5      memmove( &(A[j+1]), &(A[j]), (n-j)*sizeof(sequence::element) );
6      A[j] = tmp;
   }
}
/* better search loop (eliminates the index-in-range -- j > 0 -- test):
1   for (int j = 1; A[j] < A[n]; ++j) ;
   // Now j indexes the first entry not less than than A[n].  j = n is possible. 
*/
// better still: use binary search.