Boost logo

Boost Users :

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

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at