My instinct is that pre-sorting the incoming range is worthwhile. I will now try to convince myself otherwise: template<typename InputIterator> void insert(InputIterator first, InputIterator last) { // however it is done, I expect something like this would be worthwhile: // allocate once, enough space for all: make_room(distance(first, last)); // presorting basically tells us where to start looking when inserting the next item // ie once we insert the first pre-sorted item, we know the next one will be somewhere after that. // Is that equivalent to something like the following, where we do a similar comparison as we go? // imagine insert tells us where it was inserted // or some internal version of insert does. location = insert(first); for (i = ++first; i < last; i++) { if ( *i < *(i - 1) ) location = insert_somewhere_before(location, i); else location = insert_somewhere_after(location, i); } } Then it just looks like this is equivalent to using the previous to pick a pivot point. Which isn't any big win. Or did I do too much slight of hand there? Tony