def insertion_sort(array):
    """
    Insertion Sort
    Complexity: O(N^2)
    """
    array_len = len(array)
    for k in range(array_len):
        temp = array[k]
        i = k
        while i > 0 and temp < array[i-1]:
            array[i] = array[i-1]
            i -= 1
        array[i] = temp
    return array