title: Insert item into case-insensitive sorted list in Python
body: <p>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:</p>
  
  <pre><code>myList.append('Something')
  myList.sort(key=lambda s: s.lower())
  </code></pre>
  
  <p>But I was wondering if there is a way to just insert the item in the correct position without sorting the whole thing again.</p>
  
  <p>I found this question: <a href="https://stackoverflow.com/questions/8024571/insert-an-item-into-sorted-list-in-python">Insert an item into a sorted list in Python</a>.  It points towards Python's  <a href="https://docs.python.org/2/library/bisect.html" rel="nofollow noreferrer">bisect</a> module.  But that module doesn't look like it can support case-insensitivity.</p>
  
  <hr>
  
  <p><strong>Edit</strong>: I tested out several of the answers listed here.</p>
  
  <ul>
  <li>Appending the item to the end and sorting the whole list (as proposed in the original question) was the slowest.</li>
  <li>Moinuddin Quadri's answer was faster than sorting the whole list, but it was still pretty slow, due to running <code>lower()</code> on every item on the list.</li>
  <li>Stefan Pochmann's answer was an order of magnitude faster than sorting the whole list.</li>
  <li>Jared Goguen's answer was the fastest for repeated insertions.  The first time, though, it runs <code>lower()</code> on every element.</li>
  </ul>
  
  <p>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.</p>