Insertion Sort in Python

27 Feb 2014

Algorithms, Python

The insertion sort is a simple sorting algorithm that sorts an array (or list) one item at a time.

It is not the fastest or most efficient algorithm available, however, insertion sort does have some plusses. It's simple to implement, it is efficient for small data sets, it's in-place and online.

Put another way, unless you're working with massive datasets, an insertion sort will allow you to quickly implement a sort and allow you to get on directly with the other tasks at hand.

Here's my insertion sort implementation written in Python, used to sort an array of integers.

class Program(object):

    def InsertionSort(self, Values):
        print('Before')
        self.PrintValues(Values)

        for i in range(1, len(Values)):
            key = Values[i]
            j = i - 1
            while ((j >= 0) and (Values[j] > key)):
                Values[j + 1] = Values[j]
                j -= 1
            Values[j + 1] = key

        print('After')
        self.PrintValues(Values)

    def PrintValues(self, Values):
        for i in range(len(Values)):
            print(Values[i]),
        print('\r\n')

def main():
    oProgram = Program()
    oProgram.InsertionSort([5, 2, 4, 6, 1, 3])

if __name__ =='__main__':
    main()

The output generated by this code is:

Before
5 2 4 6 1 3

After
1 2 3 4 5 6

So, how does it work?

The basic way to visualise an insertion sort is to picture how people sort a hand of cards: they order the cards in one hand, picking unordered cards out with the other hand and inserting them back into place in the correct position. In essence, this is how an insertion sort works.

To perform an insertion sort, we create a partition that moves along the array, from left to right (lower bound to upper bound). As the partition increases, the left side sub-array is sorted. Values from the right of the partition are located and inserted into the array at the appropriate index. The sub-arrays are repositioned as required.

Using the above code as an example:

1. The partition value i begins at position 1
2. The value at position i is stored in the key variable
3. Next, all the values from i - 1 (0) are compared to the key (2), and if they are larger, they are moved one position to the right in the index
4. In this fashion, 5 is copied from position 0 to position 1 - the array now looks like { 5, 5, 4, 6, 1, 3 }
5. Our key value (2) is inserted back into the array at position j + 1 (0) - the array now looks like { 2, 5, 4, 6, 1, 3 }
6. The partition value i now begins at position 2
7. Next, all the values from i - 1 (1) are compared to the key (4), and if they are larger, they are moved one position to the right in the index
8. In this fashion, 5 is again copied up from position 1 to position 2 - the array now looks like { 2, 5, 5, 6, 1, 3 }
9. Our key value (4) is inserted back into the array at position j + 1 (1) - the array now looks like { 2, 4, 5, 6, 1, 3 }
10. The process continues

i = 1, key = 2
5	2	4	6	1	3
5	5	4	6	1	3
2	5	4	6	1	3
i = 2, key = 4
2	5	4	6	1	3
2	5	5	6	1	3
2	4	5	6	1	3
i = 3, key = 6
2	4	5	6	1	3
2	4	5	6	1	3
2	4	5	6	1	3
i = 4, key = 1
2	4	5	6	1	3
2	4	5	6	6	3
2	4	5	5	6	3
2	4	4	5	6	3
2	2	4	5	6	3
1	2	4	5	6	3
i = 5, key = 3
1	2	4	5	6	3
1	2	4	5	6	6
1	2	4	5	5	6
1	2	4	4	5	6
1	2	3	4	5	6

To summarise:

• A value is copied up the array until it meets the partition, overwriting other values in the array
• Once it's been moved to the correct position, the key value is then inserted back into the array at its correct location