### InsertionSort

In most cases, `InsertionSort` is the best of the simple sorts (i.e. `BubbleSort`, `ExchangeSort`, and `SelectionSort`).

`InsertionSort` works well if only a few elements need sorting; however, it is a poor choice if dealing with a large number of elements.

Often times `InsertionSort` is used as the final stage of more advanced sorts (e.g. `QuickSort`).

For an example of `InsertionSort`, assume we have an array `A` and its length is `N`. Let's look at pass `i` (`1 <= i <= N-1`). The sublist `A[0]` to `A[i-1]` is already sorted in ascending order. The pass assigns `A[i]` to the list. Let `A[i]` be the TARGET and move down the list, comparing the target with items `A[i-1]`, `A[i-2]`, and so forth. Stop the scan at the first element `A[j]` that is less than or equal to TARGET or at the beginning of the list (`j=0`). As we move down the list, slide each element to the right (`A[j]=A[j-1]`). When the correct location for `A[i]` is found, insert it at location `j`.

Said another way.

Assume elements are being collected using array named 'a'. The initial state is that the first element, considered by itself, is sorted. Each time a new element with value 'n' is "added" to the collection, it is inserted into a slot 'i' such that `a[i-1] <= a[i] <= a[i+1]`. If the new element is inserted into the array (i.e. it is not the last element), then the elements to the right of the insertion point must be shifted.

Many card players use the insertion sort. They are dealt a hand of cards. Each time they receive a card they place it in their hand in a sorted order. Luckily for them, shifting cards is simple. The following is an example of a card player that stores their cards in ascending order (lowest-to-highest).

```   start with an empty hand
receive an 8:  8                 //1 element is always sorted
receive a  4:  4 8               //4 is inserted, the 8 was shifted
receive a  2:  2 4 8 10          //4,8,10 all shifted
receive a  7:  2 4 7 8 10        //8,10 shifted
```

`InsertionSort` pseudo-code.

```   // assume we have an array 'a' with 'n' elements

for (cur_i = 1; cur_i < n; cur_i++) {
next_i = cur_i;
while (next_i > 0) {
if (COMPARE (a, next_i, next_i-1))
SWAP (a, next_i, next_i-1);
next_i--;
}
}
```

YouTube.com::Insertion Sort by CS50 at Harvard