It's ironic that the STL basically exists for stable sort (that's what Alex Stepanov was trying to create an efficient version of which led to most of the standard algorithms as building blocks), yet it's apparently not had much optimization focus in this standard library implementation.