def _splice(array, array_len, index, insertion, insertion_len):
    """
    We splice insertion into array at index:

    index = 1
    array = [a, b, c]
    array_len = 3
    insertion = [x, y]
    insertion_len = 2
    =>
    new_storage = [a, x, y, c]
    """
    new_len = array_len + insertion_len - 1
    assert new_len >= 0
    new_array = [None] * new_len

    for pre_index in range(index):
        new_array[pre_index] = array[pre_index]
    for insert_index in range(insertion_len):
        new_array[index + insert_index] = insertion[insert_index]
    for post_index in range(index + 1, array_len):
        new_array[post_index + insertion_len - 1] = array[post_index]

    return new_array