From: David Abrahams (dave_at_[hidden])
Date: 2007-03-18 14:21:40
on Sat Mar 17 2007, Rene Rivera <grafikrobot-AT-gmail.com> wrote:
> HervÃ© BrÃ¶nnimann wrote:
>> Rene: What do you mean by "tighter complexity bounds"? Just curious,
> I meant tighter guarantees of the complexity of the algorithm, in big O.
> The customary quicksort is usually O(NlogN) on most sequences, but it
> can be as high as O(N2). The quicksort variant I have has a guaranteed
> worst case of O(NlogN). The price for that guarantee is a larger K
> overall. Which if one is using objects for which the comparison is
> expensive is a better trade off.
How is your version different from introsort?
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk