sort() or qsort()

hi everyone,

my question is what function sort or qsort is faster, and what complexy they are.
qsort: Average: O(n log(n))
sort: I don't know any algorithm called "sort".
You can use "google" to get this information.

The C qsort() complexity is not specified, as it can be any algorithm (not necessarily quicksort).

The C++ std::sort() algorithm is usually an introsort, and should have a complexity of n log n.

If you are trying to choose which algorithm to use, go with the C++ one. You'd be wasting your time trying to optimize over that.

More on sorting can be found here. (Sorry it isn't all finished yet.)
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/

Remember, if your program is running slow, use a profiler to figure out exactly where it is running slowly.

Hope this helps.

[edit]
http://www.cplusplus.com/reference/algorithm/sort/
http://www.cplusplus.com/reference/cstdlib/qsort/
Last edited on
Thanks!

The C qsort() complexity is not specified, as it can be any algorithm (not necessarily quicksort).

I didn't knew it. Learned something more.
closed account (D4S8vCM9)
@Duoas: thanks for the faq-link, not easy to find from "normal" navigation on cplusplus.com, but useful. Will bookmark it :-D
In practice, they have the same, optimal, algorithmic complexity (n log n) but sort() is often several times faster than qsort() on equivalent data due to inlining. For example, default sort() on a container of integers will be compiled to use std::less<int>::operator(), which will be inlined and the internals of std::sort() will be comparing the integers directly. On the other hand, qsort() will be making an indirect call through a function pointer for every comparison. Sometimes compilers can optimize through that, but it's nowhere as common.
Topic archived. No new replies allowed.