Re: [boost] [iterator] std::sort on zip_iterator (repost)

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-05-09 17:00:30

On Sat, May 9, 2009 at 11:20 AM, Edouard A. <edouard_at_[hidden]> wrote:
>
> Quick/introsort requires a random access iterator, if you only have
> bidirectional iterators, merge sort is more appropriate.

Introsort requires a random access iterator for the partial_sort recursive
call, agreed.
Strictly speaking, if you're willing to iterate to the pivot point, the
Quicksort algorithm only requires a bidirectional iterator and a swap
method.  Iterating to the pivot point doesn't change the computational
complexity, nor is likely to greatly slow down the algorithm.
Thanks for the merge_sort suggestion, Edouard.

How about this:
flex_sort (if that name isn't taken)
starts with quicksort for average-case speed
after X iterations (just like introsort) switches to mergesort (as opposed
to partial_sort) for O(nlog(n)) performance
written to be as general as possible, with these requirements:
++ and -- operations that iterate
maybe support for advance if it's just as general as ++ and --
a swap method
* operator that returns either a reference or a const reference (so
comparisons can be made)

I can't think of a reason for needing to sort something that can only be
iterated forward, but if someone can give me a good argument for it, I can
eliminate the -- requirement, though it will hurt performance.
If I can't use the * operator, then I'd have to have an iter_compare method
that takes two iterators and compares them.  The extra indirection will be
slower.  In the zip_iterator example, does the * operator return a const
reference that can be used for comparison?

The calls and overloads for my suggestion would be:
flex_sort(first, last)
flex_sort(first, last, compare)
flex_sort(first, last, compare, swap)

I would expect this algorithm to be slightly slower than introsort on
average, and much slower in conditions where it switches to mergesort, but
provide substantially more flexibility with regards to what can be sorted,
and with the same order of computational complexity.
Does that sound like a useful and appropriate general solution?