Page 452 - AP Computer Science A, 7th edition

some elements may need to be moved down to create a slot.
Here is the array of four elements. In each case, the boxed element is “it,” the next element to be inserted into the sorted part
of the list. The shaded area is the part of the list sorted so far.
NOTE
1. For an array of n elements, the array is sorted after n − 1 passes.
2. After the kth pass, a[0], a[1], ..., a[k] are sorted with respect to each other but not necessarily in their final sorted positions.
3. The worst case for insertion sort occurs if the array is initially sorted in reverse order, since this will lead to the maximum possible number of comparisons and moves.
4. The best case for insertion sort occurs if the array is already sorted in increasing order. In this case, each pass through the array will involve just one comparison, which will indicate that “it” is in its correct position with respect to the sorted list. Therefore, no elements will need to be moved.
Both insertion and selection sorts are inefficient for large n.