9 May
2009
9 May
'09
7:26 p.m.
AMDG Jeremiah Willcock wrote:
Quick/introsort requires a random access iterator, if you only have bidirectional iterators, merge sort is more appropriate.
But I do have a random access iterator. The zip_iterator of multiple random access iterators is random access; it just fails to work with std::sort because its operator* does not return a "real" reference. Therefore, quicksort or introsort should work just fine with O(N lg N) complexity, but the Standard Library implementations probably won't because they make too many assumptions about references.
I'm afraid that these assumptions are written into the current standard. According to 24.1.3 you do not even have a forward iterator. In Christ, Steven Watanabe