I am trying to determine the time complexity (and space complexity if anyone would like to have a go at it) of a sort function i implemented with a custom comparator. it is the sort function from the STL <algorithm>. First off, I am using Visual C++, so I am assuming it uses the standard C++ sort, which from what I have read on the web has an average complexity of N*log(N) and a worst case of N^2. Now, here is the implementation:

```
bool by_length (const string& s1, const string& s2) {
if ( s1.length() == s2.length() )
return lexicographical_compare( s1.begin(), s1.end(), s2.begin(), s2.end() );
return s1.length() < s2.length();
}
int main() {
vector<string> v;
//populate vector here....
sort(v.begin(), v.end(), by_length);
return 0;
}
```

Now, i have also read that lexicographical_compare (another STL <algorithm>) runs in linear time. I am looking for best case, average case, and worst case. Now, an affecting factor is that there may be anywhere from no strings with the same length in the vector up to all strings having the same length. any help is appreciated. also, if anyone has any tips on optimization, that is appreciated also.