Ali Çehreli:
If an array is sorted every time an element is added,
Items are most times added at the end, and they respect the sortness of the whole array. The array never gets sorted.
On the other hand, array wins if the insertions are batched and
Insertions are not batched, and they are interspersed with searches. This is the common use case.
As Max Klyga said, that single sort better be applied on the container, not on the range.
The container unfortunately doesn't know it is sorted, so I have to verify the sortness invariant manually, and before the search I need to use an assumeSorted(). This is not good.
Bye, bearophile
