Boost logo

Boost Users :

Subject: Re: [Boost-users] Quick Sort
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-04-05 19:12:13


At Tue, 5 Apr 2011 18:40:02 -0300,
Murilo Adriano Vasconcelos wrote:
>
> > > Can some one point me to a implementation of Quicksort or like algorithms
> > > using boost library
> >
> > std::sort() ?
> >
>
> I think that the algorithm used under std::sort() is implementation detail.
> The only specification is that it must be O(N log N) in average case. For
> example, the sorting algorithm used in GNU Standard C++ Library's
> std::sort() is the introsort algorithm, not quicksort.

In practice that means it's either using quicksort or introsort (until
it gets to the leaves, where it might be doing insertion sort). And
introsort is just quicksort until it starts to go pathological. So
I'd say, apart from it not being in Boost, the answer "std::sort" is a
pretty good one.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net