Before C++11:
std::sort must have average case linearithmic (n log n) time complexity. Any algorithm may be used so long as that time complexity requirement is met. There is no worst case time complexity requirement.
If you want a guaranteed worst case time complexity function, use std::stable_sort, which has quasilinear worst case time complexity (n log^2 n).