Comment by eniotna

In most real world problems, you don't really care about keeping a data structure sorted at all time. All you want, is to have it sorted when you're about to do X. So it's generally faster to just have a contiguous chunk, insert at the end, then sort when you need.