# What sorting algorithm does STL use?

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?

-
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. –  delnan May 17 '12 at 18:22
@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. –  Mason Wheeler May 17 '12 at 18:26
@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. –  Mert May 17 '12 at 18:35
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. –  delnan May 17 '12 at 19:03
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.) –  chrisaycock May 17 '12 at 20:27

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.

-

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.

-

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.

-
oh really, what about TwoUniqueSort :) critticall.com/sort.html. But yeah... for mainstream, STL is as good as you should need it to be. –  DXM May 17 '12 at 18:38
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). –  delnan May 17 '12 at 18:59

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.

-