Beating TimSort at Merging
Here is a problem. You are tasked with improving the hot loop of a Python program: maybe it is an in-memory sequential index of some sort. The slow part is the updating, where you are adding a new sorted list of items to the already sorted index. You need to combine two sorted lists and keep the result sorted. How do you do that update?
Source: Beating TimSort at Merging, an article by Adam Gordon Bell.
See also Past TimSort threads, for anyone interested, a Hacker News comment.