Insert a number in a sorted list and return the list with the number at the correct index

Question

I feel like the title is a bit wordy. What I have defined here is a function that takes two parameters:

• a list that contains valued sorted from smallest to biggest
• a number to insert at the right index so that the returned list print its values from smallest to biggest

NOTE: Recursion is mandatory

def insert(lst, to_insert):
    """
    parameters : lst of type list, that contains values sorted from smallest to largest;
                 to_insert : represents a value 
    returns : same list with the to_insert value positioned at the right index
              in order for the list to remain sorted from smallest to largest;
    """
    if len(lst) == 1:
        return []
    if lst[0] < to_insert and to_insert < lst[1]:
        lst[3] = to_insert
        return [lst[0]] + [lst[3]] + insert(lst[1:], to_insert)
    else:
        return [lst[0]] + insert(lst[1:], to_insert)

print(insert([1,2,3,4,5,7,8,9], 6))

The list outputs the following :

[1,2,3,4,5,6,7,8]   #not sure where 9 got left

How do I optimize this function, using only simple functions.

Answer 1

if len(lst) == 1:
    return []

This is incorrect, as it crops one number off and produces the 9 bug you have seen. Instead, you can do:

if not lst:
    return [to_insert]

Similarly, the remaining of the function is overly complicated, and can return false results in some edge cases. You would have problems calling for lst[3] if the list is not of four elements or more, and I believe it's incorrect too when inserting 1 in [2, 3, 4, 5].

if lst[0] > to_insert:
    return [to_insert] + lst
return [lst[0]] + insert(lst[1:], to_insert)

Would be more correct, although not optimal.

Answer 2

Recursion is usually a poor choice in Python. Non-tail recursion is usually a poor choice in any language (and this is non-tail because we apply + to the result before returning it).

It's better to use the standard bisect module to find (once) the correct index at which to insert. This module provides the bisect() function to locate the correct index, and also the insort() function that calls bisect and then inserts, exactly as we want:

insert = bisect.insort

This will insert in place, rather than creating a new list, so not exactly equivalent to the existing code.

---

As you say "using only simple functions", let's suppose you can't use the Standard Library (that's a bad assumption in general - Python philosophy is that it "includes batteries" to make your code simpler). Then we can use a similar method to write our own non-recursive version.

def insert(lst, to_insert):
    """
    parameters : lst: sorted list (smallest to largest)
                 to_insert: value to add
    returns : copy of lst with the to_insert value added in sorted position
    """

    # binary search
    left = 0
    right = len(lst)

    while left != right:
        mid = left + (right-left) // 2
        if lst[mid] == to_insert:
            left = right = mid
        elif lst[mid] < to_insert:
            left = mid + 1
        else:
            right = mid

    # now copy the list, inserting new element
    return lst[:left] + [to_insert] + lst[left:]

---

Since the question states (without justification) that "recursion is mandatory", I recommend making the search recursive, but performing the insertion just once:

#! untested
def insert(lst, to_insert, left=0, right=None):
    if right is None:
        right = len(lst)

    if left == right:
        return lst[:left] + [to_insert] + lst[left:]

    else:
        mid = left + (right-left) // 2
        if lst[mid] == to_insert:
            left = right = mid
        elif lst[mid] < to_insert:
            left = mid + 1
        else:
            right = mid
        # move left or right, then
        return insert(lst, to_insert, left, right)

This is now tail-recursive, at least, and only reallocates the list elements once, rather than every level of recursion.