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

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.

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.

• What does the line return [to_insert] + lst do? – Mister Tusk Nov 12 '18 at 17:14
• @MisterTusk It returns the list prepended with the element to_insert. For example if to_insert is 1 and lst is [2, 3, 4], it will return [1, 2, 3, 4]. – Arthur Hv Nov 12 '18 at 19:02

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)
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.

• I suppose this is a programming exercise. – Arthur Hv Nov 12 '18 at 17:05
• Could be - that said, looking at how they work might be instructive. – Toby Speight Nov 12 '18 at 17:06