larshagencpp

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.

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.

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.