I understand that it is not random access according to the standard. What I was saying is that algorithm-wise (in terms of writing them from scratch), the iterator can be treated as having actual random access (with the new iterator hierarchy), even though it does not satisfy the requirements that are part of the specification for std::sort and such. That is, it satisfies some requirements (constant-time +=, etc), and the deficiencies can be worked around in a newly-written sorting algorithm. The discussion was about whether to use quick sort or merge sort, and either of these would be efficient on zip_iterators if they were rewritten to handle the swap problem.
Ok now I clearly see the problem. You need a sort algorithm that takes the dereference to the element and the swap as template policy parameters. One could write a specialized sort, but I think it would be even nicer to have a customizable introsort (ie you could customize the pivot selection, thresholds, fallback algorithms, comparison, dereference and maybe other things). Performances would probably be a tiny bit below std::sort (because inlining doesn't always work as expected) but you would use it when std::sort doesn't work, or when you are in a case where the default pivot (generally median of 3 or median of 5) is suboptimal for you. As for quicksort vs mergesort (I would include heapsort in the comparison as well) I would bet on quicksort, but benchmarking is the only way to know. -- EA