# Insertion Sort

The insertion sort algorithm relies on the following strategy:

1. Suppose the first $k$ elements are ordered from least to greatest, even though these elements are not necessarily in their final positions with respect to the entire array.
2. Move the $(k+1)^{th}$ element left (via repeated swaps) until the first $(k+1)$ elements are ordered from least to greatest.
3. Repeat until done.

An example is shown below:

5 2 4 1 9 3 7  Notice the very short subarray consisting
* ^            of 5 is (trivially) "in order" and 2 is to
its immediate right

Now we compare 2 with its left neighbor repeatedly,
swapping the two if they are out of order...

5 2 4 1 9 3 7  swap, as 5 > 2
- ^

2 5 4 1 9 3 7  2 moved as far left as it could, so
* * ^          the first 2 elements are now "in order"
and 4 is to their immediate right

Now we compare 4 with its left neighbor repeatedly,
swapping the two if they are out of order...

2 5 4 1 9 3 7  swap, as 5 > 4
- ^

2 4 5 1 9 3 7  do not swap, as 2 < 4
- ^

2 4 5 1 9 3 7  4 moved as far left as it could, so
* * * ^        the first 3 elements are now "in order"
and 1 is to their immediate right.

Now we compare 1 with its left neighbor repeatedly,
swapping the two if they are out of order...

2 4 5 1 9 3 7  swap, as 5 > 1
- ^

2 4 1 5 9 3 7  swap, as 4 > 1
- ^

2 1 4 5 9 3 7  swap, as 2 > 1
- ^

1 2 4 5 9 3 7  1 moved as far left as it could, so
* * * * ^      the first 4 elements are now "in order"
and 9 is to their immediate right.

Now we compare 9 with its left neighbor repeatedly,
swapping the two if they are out of order...

1 2 4 5 9 3 7  do not swap, as 5 < 9
- ^

1 2 4 5 9 3 7  9 moved as far left as it could (it couldn't at all), so
* * * * * ^    the first 5 elements are now "in order"
and 3 is to their immediate right.

Now we compare 3 with its left neighbor repeatedly,
swapping the two if they are out of order...

1 2 4 5 9 3 7  swap, as 9 > 3
- ^

1 2 4 5 3 9 7  swap, as 5 > 3
- ^

1 2 4 3 5 9 7  swap, as 4 > 3
- ^

1 2 3 4 5 9 7  do not swap, as 2 < 3
- ^

1 2 3 4 5 9 7  3 moved as far left as it could, so
* * * * * * ^  the first 6 elements are now "in order"
and 7 is to their immediate right.

Now we compare 7 with its left neighbor repeatedly,
swapping the two if they are out of order...

1 2 3 4 5 9 7  swap, as 9 > 7
- ^

1 2 3 4 5 7 9  do not swap, as 5 < 7
- ^

1 2 3 4 5 7 9  7 moved as far left as it could, so
* * * * * * *  all the elements are not "in order".
Given there are not more elements to
the right, we stop.


### Implementation and Analysis

The implementation of an insertion sort, as shown below, is straight-forward -- especially with the helper methods less() and exch().

    public static void insertionSort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j--) {
if (less(a[j], a[j-1])) {
exch(a, j, j-1);
}
else {
break;
}
}
printOrder(a);
}
}


To analyze the efficiency of this algorithm, we again resort to counting the number of comparisons and exchanges. In the best case, when the list is already in order, note that the algorithm makes $n-1$ comparisons. These are required to verify that each element need not be moved to the left. Of course, if no element moves, there are zero exchanges.

In the worst case (reverse order), the $2^{nd}$ element must be compared with $1$ element, the $3^{rd}$ element must be compared with $2$ elements, the $4^{th}$ with $3$ elements, the $5^{th}$ with $4$, and so on -- until the last element must be compared with the other $n-1$. Thus there is a total number of comparisons equal to the following:

$$1 + 2 + 3 + \cdots + (n-2) + (n-1) = \frac{n(n-1)}{2} \sim \frac{n^2}{2} = O(n^2)$$

Since in the worst case, every comparison results in an exchange, the number of exchanges is also $O(n^2)$.

In the average case, the number of comparisons and exchanges are both smaller (both are $\sim n^2/4$), as elements aren't as far from their final positions as they are when the array is in reverse-order.

Consequently, the insertion sort reduces the number of comparisons from that seen with the selection sort, but at the cost of more exchanges.