Re: [Boost-users] Quick Sort

Subject: Re: [Boost-users] Quick Sort
From: rpuri6_at_[hidden]
Date: 2011-04-05 19:55:20

thanks 

----- Original Message ----- 
From: "Dave Abrahams" <dave_at_[hidden]> 
To: boost-users_at_[hidden] 
Sent: Tuesday, April 5, 2011 4:12:13 PM 
Subject: Re: [Boost-users] Quick Sort 

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 mailing list 
Boost-users_at_[hidden] 
http://lists.boost.org/mailman/listinfo.cgi/boost-users