Author here. Longish article but I wanted to make a fairly comprehensive reply to those who have doubted SortedContainers' ability to scale. If you jump down to the benchmarks section, you'll see the performance at 10,000,000,000 (ten billion) elements. I ended up paying $40 to rent a highmem instance on GCE for 1,011 minutes to run the benchmarks. For those curious, the memory high-water mark was ~128GB using PyPy. These results would be a lot more expensive to replicate with any other sorted collections library today.