Performance of std::partial_sort() versus std::sort() when sorting the whole range?

Viewed 2859

Is there a significant difference between the following two approaches? Way 1 uses sort or partial_sort, depending on the size of the vector while way 2 always uses partial_sort. I find way 2 more appealing because my predicate is a bit more complicated than in the example, so I don't want to repeat it. But I wonder if partial_sort performs worse than sort because it is not meant to be used to sort the whole range, which is why I tend to use way 1.

int main()
{
  std::vector<double> vec;
  vec.push_back(1.0);
  vec.push_back(3.0);
  vec.push_back(2.0);
  vec.push_back(5.0);
  vec.push_back(4.0);
  vec.push_back(9.0);
  const size_t numBest = 3;
  const size_t numTotal= vec.size();

#if WAY1
  if (numTotal < numBest)
  {
    std::sort(vec.begin(), vec.end(), std::not2(std::less<double>()));
  }
  else
  {
    std::partial_sort(vec.begin(), vec.begin() + numBest, vec.end(), std::not2(std::less<double>()));
    vec.resize(numBest);
  }
#elif WAY2
  {
    const size_t numMiddle = numTotal < numBest ? numTotal : numBest;
    std::partial_sort(vec.begin(), vec.begin() + numMiddle, vec.end(), std::not2(std::less<double>()));
    vec.resize(numMiddle);
  }
#endif

  // now vec contains the largest numBest results.
  return 0;
}

Some testing yielded that partial_sort is significantly worse (factor of 4 in my usecase) than sort if if has to sort the whole range. This indicates that way 1 is to be preferred. It seems that partial_sort is only meant for sorting a small fraction of the whole range. I tested in Visual Studio 2010.

2 Answers
Related