def insertion_sort(array):
    """Insertion sort."""
    length = len(array)
    for i in range(1, length):
        val = array[i]
        while i > 0 and array[i - 1] > val:
            array[i] = array[i - 1]
            i -= 1
        array[i] = val
    return array