In Chapter 1 of *Introduction to Algorithms* the authors introduce a general insertion sort algorithm for sorting a small number of elements in an array written in pseudocode. The following is a simple port to Python:

```
for index in range(len(instance)):
value = instance[index]
element = index - 1
# Insert instance[index] into the sorted sequence
while element >= 0 and instance[element] > value:
instance[element + 1] = instance[element]
element = element - 1
instance[elment + 1] = value
```

There are two notable differences from the original. Python does not allow iteration over the integer returned by the length function on line 1, which is why I added the range function. The second difference is the first operator on line 5, which originally read as follows:

` while i > 0 and A[i] > key`

This assumes that the index of the first element in the array is 1. However, in Python list indices start at 0. The algorithm would still run with the greater than operator, but the script will not sort the first element in the array, because it does not match the while loop. For example, the list `[5, 2, 4, 6, 1, 3]`

would return `[5, 1, 2, 3, 4, 6]`

.