[Mingw-users] Re: qsort speed

[Alex V. <al...@co...>]

"Greg Chicares" <chi...@mi...> wrote in message news:3FF...@mi......
> Jan Ringos wrote:
> >
> > I worry about its speed more than its portability.
>
> It's one of the fastest sorting algorithms, except in cases
> where it's terribly slow. Consider using std::stable_sort(),
> which the C++ standard guarantees to be O(N log N) if enough
> memory is available.
>
> But always look at the library implementation and measure the
> speed yourself. According to SGI's STL documentation, their
> std::stable_sort uses MergeSort, and their std::sort uses
> IntroSort, and they give the same order of complexity for both
> as for QuickSort (provided there's enough memory). Yet order
> of complexity doesn't measure absolute speed.
>
> > But now I am really disappointed when I know it's written by
> > Microsoft :-)
>
> Probably they hired someone competent to write it for them.
> And if they didn't do a good job at first, then probably it's
> been fixed by now. Their C runtime library is old enough that
> it should be of good quality, at least for the C89-90 language.
>
> Yet a C++ template implementation might have better performance:
>   http://www.tantalon.com/pete/cppopt/final.htm
>   "In one oft-cited case, the C++ standard library sort ran 7
>   times faster than qsort on a test of 500,000 elements because
>   the C++ version was inlined."
> When speed matters, there's no substitute for measurement.

[snip]

Here are some results of measurements related to sort issue :

http://article.gmane.org/gmane.comp.lang.c%2B%2B.perfometer/17


--
   Alex Vinokur
     mailto:al...@co...
     http://mathforum.org/library/view/10978.html