Best Case, O(n)

Worst Case, Ω(n^2)

Memory Complexity, O(1)

#!/usr/bin/python

import random

def insert_sort(l):
    n = len(l)

    for i in range(1, n):
        key = l[i]
        j = i-1

	# Insert l[j+1] into the sorted sequence l[0 ... j]
        while j >= 0 and l[j] > key:
            l[j+1] = l[j]
            j -= 1
        l[j+1] = key

def get_list():
    random.seed()

    l = []
    for i in range(10):
        l.append(random.choice(range(10)))

    return l

def main():
    l = get_list()
    print(l)

    insert_sort(l)
    print(l)

if __name__ == '__main__':
    main()