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.