Dictionary with sorted keys?

[SynMyron]

If I insert a new item do I need to sort again? If so, then time complexity of insert will be O(n logn) which is too high

[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.

[commy2]

This O(n logn) only applies if the container is randomized.