Insertion Sort

def insertion_sort(collection):
    """Pure implementation of the insertion sort algorithm in Python

    :param collection: some mutable ordered collection with heterogeneous
    comparable items inside
    :return: the same collection ordered by ascending

    Examples:
    >>> insertion_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]

    >>> insertion_sort([])
    []

    >>> insertion_sort([-2, -5, -45])
    [-45, -5, -2]
    """
    def swap(i, j):
        collection[i], collection[j] = collection[j], collection[i]

    for i in range(1, len(collection)):
        insertion_index = i
        while (
            insertion_index > 0 and
            collection[insertion_index - 1] > collection[insertion_index]
            ):
            swap(insertion_index, insertion_index-1)
            insertion_index -= 1

    return collection