insertion_sort.py

# Insertion Sort Algorithm - sorts a sequence in place, for additional 
# convenience returns the sequence.
# Time complexity: n^2

# For descending sort change the comparison symbol on line 18:
# while i >= 0 and seq[i] < key

# Script is intended to be run with Python3, but is Python2 compatible.
# If running the script with Python2, range() function will return a list.
# Consider changing it to xrange(), if running with Python2.
from __future__ import print_function


def insertion_sort(seq):
    for j in range(1, len(seq)):
        key = seq[j]
        i = j - 1
        while i >= 0 and key < seq[i]:
            seq[i+1] = seq[i]
            i -= 1
        seq[i+1] = key
    return seq


if __name__ == '__main__':
    seq = [4, 2, 9, 5, 3, 0, 7]
    print(insertion_sort(seq))