def insertion_sort(array):
    """
    Sort an input array with insertion sort algorithm

    The insertion sort algorithm compares an element with the preceeding
    ordered element to determine whether the two should be swapped.  This will
    continue until the preceeding element is no longer greater than the
    current element.

    Best case scenario: O(n)
    - Best case, if an array is already sorted, this algorithm will inspect
    every element of the list once to verify it is sorted, no swaps required.

    Worst case scenario: O(n^2)
    - Worst case, if an array is reversely sorted, each element must be
    compared and swapped with every element preceeding it until it reaches
    the beginning.
    """
    for elem in range(len(array)):
        curr = elem
        while curr > 0 and array[curr - 1] > array[curr]:
            # swap values
            array[curr - 1], array[curr] = array[curr], array[curr - 1]
            curr -= 1
    return array