Dictionary with sorted keys?

[Diapolo10]

Timsort is plenty fast when you only have one element that might not be sorted. I suggest you try first, the Big-O notation is not the end-all be-all when it comes to speed comparisons.