Почему я получаю квадратичную сортировку по времени с помощью STL sort ()?

Я пытался отсортировать вектор объектов по значениям, хранящимся на карте, используя функцию STL sort (). К моему большому удивлению, мой алгоритм работал в квадратичном времени. Я упростила его настолько, насколько могла, пытаясь выявить явную ошибку, но безрезультатно. Вот упрощенная версия:

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

struct a{
map<a*,float> vals;
bool operator()(a* a1, a* a2){return (vals[a1]>vals[a2]);}
void asort();
};

void a::asort(){
vector<a*> v;
map<a*,float>::iterator it = vals.begin();
for(;it!=vals.end();it++){v.push_back((*it).first);}
sort(v.begin(),v.end(),*this);
}

int main(){
a a0;
int imax=8000;
for(int i=0;i<imax;i++){a0.vals[new a]=rand();}
a0.asort();
}

Когда я запускаю его для imax = 2000, 4000, 8000, это занимает около 1 с, 4 с, 18 с соответственно. Как это возможно? Почему я не получаю ожидаемую зависимость imax * log (imax)? У меня ограниченный опыт работы с C ++, пожалуйста, помогите! Спасибо!

Обновить: спасибо Ксео, Рик и всем, кто откликнулся. Как объясняли Ксео и Рик, проблема в том, что компаратор (в моем случае struct a с картой, содержащей значения) копируется при каждом сравнении, следовательно, вычислительная сложность O(imax^2 log(imax)), Один из способов обойти это (чтобы изменения в моем коде были минимальными) — использовать указатель на карту, а именно: map<a*,float>* vals, вместо map<a*,float> vals, Тогда копирование карты исключается, и сложность возвращается к O(imax log(imax)), Большое спасибо!