Why do I get quadratic time sorting using STL sort()?

Question

I was trying to sort a vector of objects by values stored in a map, using the STL sort() function. To my great surprise, my algorithm was running in quadratic time. I simplified it as much as I could, trying to pinpoint an apparent bug, but to no avail. Here is the simplified version:

#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();
}

When I run it for imax=2000, 4000, 8000, it takes about 1s, 4s, 18s respectively. How is this possible? Why don't I get the expected imax*log(imax) dependence? I have limited experience with C++, please help! Thanks!

Update: thank you Xeo, Rick and everyone who responded. As Xeo and Rick explained, the problem is that the comparator (in my case struct a with the map containing values) gets copied on each comparison, hence the computational complexity O(imax^2 log(imax)). One way around this that I can see (so that changes to my code are minimal) is to use a pointer to the map, namely map<a*,float>* vals, instead of map<a*,float> vals. Then the map copying is avoided, and the complexity is back to O(imax log(imax)). Thanks a lot!

Answer 1

std::sort takes its predicate by value, meaning

sort(v.begin(),v.end(),*this);
//                     ^^^^^

will copy the contained map.

Next, you're doing a map lookup twice during the comparision, which is O(log N), while it's expected that pred(a,b) is a constant operation.

You can fix this by defining a seperate comparator for std::sort and using std::unordered_map (C++11).

Answer 2

A map is already sorted. std::sort is probably based on Quicksort, whose worst-case performance is when the input is pre-sorted.