What sorting algorithm does STL use?

Question

I recently started using <vector.h> library and I was wondering, since all the operations are already implemented, IF the method of the sorting algorithm is the most efficient one. Everything runs perfect, there is no doubt, but should I worry about its performance?

If I want to sort up to 6-7 million numbers, should I implement my own sorting method using quick sort?

• user7043: The title is the wrong question you mention later. You don't (or at least shouldn't) care which algorithm it uses, only whether it's fast enough for your use case.
• Mason Wheeler: @delnan: There are more issues to consider than just being fast. There's additional memory consumption, stability (will two items that compare equal on the sort criteria remain in the same order relevant to each other?) and best case/worst case/average case issues. For example, for best case and average case, Quicksort is easily the fastest, but it's one of the worst of the common sorting algorithms when measured against pretty much every other criterion. So yeah, algorithm choice does matter.
• Mert Akcakaya: @delnan How can one know if it suits his use case without knowing the underlying algorithm? Each sorting algorithm has some worst and best case scenarios. You want to choose your sorting algorithm considering your data collection's properties.
• user7043: Yes, there are other performance metrics than time, sorry I glossed about that. But one can check any of those performance metrics very reliably by measuring rather than thinking about the algorithm - and you even learn about constant factors! Asymptotic complexity only tells you that much. @Mert Just measure with different data sets! Ideally, measure with one that matches the data you actually care about. Sure, it won't tell you how the algorithm behaves if the input size explodes, but that does not seem to be a concern.
• chrisaycock: I hope you aren't using <vector.h>! Standard C++ moved to <vector> back in the late '90s. All of the standard headers now omit the .h that standard C uses. (In contrast, Boost uses .hpp, which is what a lot of new C++ code uses outside the standard library.)

Answer 1

In most libraries, std::sort is implemented as an introsort, so unless you want to hurt worst-case performance (a lot), you almost certainly do not want to use Quicksort instead. My experience indicates that a home-rolled Quicksort will rarely improve performance noticeably anyway.

The main reason to switch to something else would be to get something like stability (in which case you want std::stable_sort instead) or ability to work with data that won't fit in RAM (in which case you might want to look into STXXL), not for simple performance.

Answer 2

It's hard to be definitive without knowing your use-case in detail, but as a general rule of thumb;

Don't optimise early

Implement the simplest, most readable and maintainable solution first, and then benchmark it. Often it will be plenty fast enough. You should only start worrying about optimisation when there is a problem, and when you have done enough benchmarking to know where the problem lies.

Answer 3

Sorting algorithms performs different based on your data collection's certain properties.

You say you just started using , so you won't likely to write faster sorting algorithms than people who created C++ and its libraries. Use standard libraries.

Answer 4

It is unlikely you will be able to create a sort faster than std::sort in most cases. its even faster than the C qsort() in many cases.

• DXM: oh really, what about TwoUniqueSort :) critticall.com/sort.html. But yeah... for mainstream, STL is as good as you should need it to be.
• user7043: std::sort is faster because the compiler can inline the comparision (rather than using a function pointer), not because of the algorithm used. In C++, it's simple to add that optimization in any algorithm you implement yourself (use a template).