Insertion Sort

Insertion Sort takes advantage of the following fact.

If A < B and B < C, then it follows that A < C. We can skip the comparison of A and C.

Consider the following partially sorted list of numbers.

2 5 8 3 9 7

The first three values of the list are sorted. The 4th value in the list, (3), needs to move back in the list between the 2 and 5.

This involves two tasks, finding the correct insert point and a right shift of any values between the start and insertion point.

The code follows.

void insertionSort(ArrayList <Integer> list){
  for (int outer = 1; outer < list.size(); outer++){
    int position = outer;
    int key = list.get(position);

    // Shift larger values to the right
    while (position > 0 && list.get(position - 1) > key){
      list.set(position, list.get(position - 1));
      position--;
    }
    list.set(position, key);
  }
}

By default, a list of one number is already sorted. Hence, the outer loop skips position 0 and ranges from positions 1 to list.size(). For the sake of discussion, let us assume a list of 6 numbers.

For each pass of outer, the algorithm will determine two things concerning the value stored in list[outer]. First, it finds the location where list[outer] needs to be inserted in the list. Second, it does a right shift on sections of the array to make room for the inserted value if necessary.

Constructing the inner while loop is an appropriate place to apply DeMorgan’s laws:

1. The inner while loop postcondition has two possibilities:
   The value (key) is larger than its left neighbor.
   The value (key) moves all the way back to position 0.

2. This can be summarized as:

   (0 == position || list.get(position - 1) <= key)

3. If we negate the loop postcondition, we get the while loop boundary condition:

   (0 != position && list.get(position - 1) > key)

4. This can also be rewritten as:

   ((position > 0) && (list.get(position - 1) > key))

The two halves of the boundary condition cover these situations:

(position > 0) -> we are still within the list, keep processing

list[position - 1] > key -> the value in list[pos-1] is larger than key, keep moving left (position--) to find the first value smaller than key.

The Insertion Sort algorithm is appropriate when a list of data is kept in sorted order with infrequent changes. If a new piece of data is added, probably at the end of the list, it will get quickly inserted into the correct position in the list. Many of the other values in the list do not move and the inner while loop will not be used except when inserting a new value into the list.