Inserting in order to a nested list

Question

Say I had a nested list like so:

nested_list=[[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me=[122,'George','AL']

The list is currently sorted (In alphabetical order) by the middle value of each sublist, I want to add the value insert_me in its correct place in the nested list. In order to maintain alphabetical order it needs to be added between the lists with 'Bob' and 'John' in them. I know bisect would normally be used for a task like this with lists but don't understand how I could use bisect for a nested list like this.

Answer 1

See the example in the Python documentation for bisect:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficient design (successive calls to bisect functions would not “remember” all of the previous key lookups).

Instead, it is better to search a list of precomputed keys to find the index of the record in question:

>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambda r: r[1])
>>> keys = [r[1] for r in data]         # precomputed list of keys
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
('blue', 1)
>>> data[bisect_left(keys, 5)]
('red', 5)
>>> data[bisect_left(keys, 8)]
('yellow', 8)

So in your case:

nested_list = [[123,'Aaron','CA'],[124,'Bob','WY'],[125,'John','TX']]
insert_me = [122,'George','AL']                                
keys = [r[1] for r in nested_list]
nested_list.insert(bisect.bisect_left(keys,insert_me[1]),insert_me)
[[123, 'Aaron', 'CA'],
 [124, 'Bob', 'WY'],
 [122, 'George', 'AL'],
 [125, 'John', 'TX']]

To avoid rebuilding the keys everytime, insert new values into keys as well:

keys.insert(bisect_left(keys,insert_me[1]),insert_me[1])

---

Update:

Did some performance comparison between insert/bisect, append/sorted and heapq solutions:

# elements  heapq   insert/bisect  append/sorted
10,000      0.01s   0.08s           2.43s         
20,000      0.03s   0.28s          10.06s
30,000      0.04s   0.60s          22.81s