Re: [Boost-users] Quick Sort

Subject: Re: [Boost-users] Quick Sort
From: Murilo Adriano Vasconcelos (muriloufg_at_[hidden])
Date: 2011-04-05 19:16:38

2011/4/5 Dave Abrahams <dave_at_[hidden]>

> At Tue, 5 Apr 2011 18:40:02 -0300,
> Murilo Adriano Vasconcelos wrote:
>
> 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.
>
>
 Yes, I missed the "or like" part.
-- 
Murilo Adriano Vasconcelos
http://murilo.wordpress.com