Insert item into case-insensitive sorted list in Python

Question

I have a list of strings that is already sorted in case-insensitive order. I would like to insert a new string into the list. One way to do this is to append the item and then sort the list, like so:

myList.append('Something')
myList.sort(key=lambda s: s.lower())

But I was wondering if there is a way to just insert the item in the correct position without sorting the whole thing again.

I found this question: Insert an item into a sorted list in Python. It points towards Python's bisect module. But that module doesn't look like it can support case-insensitivity.

---

Edit: I tested out several of the answers listed here.

• Appending the item to the end and sorting the whole list (as proposed in the original question) was the slowest.
• Moinuddin Quadri's answer was faster than sorting the whole list, but it was still pretty slow, due to running lower() on every item on the list.
• Stefan Pochmann's answer was an order of magnitude faster than sorting the whole list.
• Jared Goguen's answer was the fastest for repeated insertions. The first time, though, it runs lower() on every element.

It was a close call to accept an answer. In the end, I went with Stefan Pochmann's answer because it was the best for a one-time insertion, and accessing the resulting list does not require accessing a member variable. However, use cases vary, so be sure to examine all the answers.

Answer 1

It's a good opportunity to practice binary search again (or just copy&paste&modify bisect.insort, which is what I did):

def insort_case_insensitive(a, x):
    key = x.lower()
    lo, hi = 0, len(myList)
    while lo < hi:
        mid = (lo + hi) // 2
        if key < a[mid].lower():
            hi = mid
        else:
            lo = mid + 1
    a.insert(lo, x)

Demo:

myList = ['a', 'b', 'c', 'd', 'e']
for x in 'A', 'B', 'C', 'D', 'E':
    insort_case_insensitive(myList, x)
print myList

Prints:

['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E']

It's O(n), just like append+sort would be, but only because of the a.insert(lo, x) at the end. Which is dead-simple and done in C, so it's super fast. The binary search of course only takes O(log n) steps, so that's super fast as well. The append+sort way would call .lower() on all elements and compare them, both of which is much slower. @MoinuddinQuadri's first solution is also much slower because of calling .lower() on all elements.

See my other answer for a benchmarking comparison.

Answer 2

You may use bisect.bisect on the lower-cased sorted list as:

from bisect import bisect
my_list = ["aa", "bb", "Dd", "ee"]
insert_string = "CC"

#                 convert all the items in list to lower case for
#               v finding the correct location via. bisect
index = bisect([i.lower() for i in my_list], insert_string.lower())
#                bisect based on lower-cased string for  ^
#                case-insensitive behavior

my_list.insert(index, insert_string)

where updated content of my_list will be:

['aa', 'bb', 'CC', 'Dd', 'ee']