Insertion sort algorithm is a simple algorithm, its an iterative algorithm, without incurring recursive. Because it didn't take the divide and conquer approach. It just compare and move elements around in the array.

I had written it in PHP.

```
function insertion_sort(\$A)
{
for (\$j = 2 ; \$j <= count(\$A) ; \$j++)
{
\$key = \$A[\$j-1];// from 1 to length - 1
\$i = \$j - 1;
for(; \$i > 0 && \$A[\$i - 1] > \$key;)
{
\$A[\$i] = \$A[\$i - 1];
\$i = \$i - 1;
}

\$A[\$i ] = \$key;
}
}
```

I was trying to implement it in Python. Two new things learned. First one is the for in range of Python didn't include the last one. And for the conditional loop, while statement is better.

```
import unittest
def insertion_sort(list):

#from 1 to len(list) - 1
for j in range(1, len(list) ):

key = list[j]
i = j - 1

while i >= 0 and list[i] > key:
list[i + 1] = list[i]
i = i - 1
#pos i + 1 is the pos we insert key
list[i + 1] = key

class test_insertionsort(unittest.TestCase):
def setUp(self):
self.list = [23,1,23,3,353,454,654,46,56757,57,5]
def tearDown(self):
del self.list
def test(self):
insertion_sort(self.list)
print self.list
for i,v in enumerate(self.list):
if i < len(self.list) -1:
self.assertTrue(v <= self.list[i + 1])

if __name__ == "__main__":
unittest.main()

```

The second version set the j start from 1, its better than start from 2.