On Sat, May 9, 2009 at 11:20 AM, Edouard A. <edouard@fausse.info> 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?