Changed to "high performance" :) I don't have a strong opinion myself, as english is not my primary language, but I appreciate the input.

This is the reason that the problem was simplified to using vector<pair<int,int>> for all the experiments, so no difference in data size.

How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but maybe you mean something different.

The items are sorted after each insertion.

Yes, but the incrmental sorting problem requires that the k elements are not only sorted, but are the k first elements of the whole sequence of length N.

Why does that make a difference? Every insertion into an RB tree self-balances and sorts the elements. So if you sort the first k elements (insert them in the tree), sorting the next element is fairly cheap (log k). Maybe I'm misunderstanding what you mean.