You'd have to use a specialized sorting algorithm that does not dereference any elements and does not use std::swap. To make it as general as possible, I think it would be best to define a simple_sort that works on bidirectional iterators and lets the user override the swap method to allow tuple swapping, for example. The idea is a fallback sort that can sort almost any sortable data structure, though not necessarily at optimal speed. You're welcome to write this yourself, possibly using the quicksort part of the STL introsort definition, or you could wait for me to write it, which I should eventually get to.
Quick/introsort requires a random access iterator, if you only have bidirectional iterators, merge sort is more appropriate. It's very easy to implement using std::merge (or std::inplace_merge for a speed/memory tradeoff) : - If the list is small (below 30 ?) - use insert_sort - else - Part the list in two at the middle - Call merge sort on each part (recursion here) - std::merge (or std::inplace_merge) the two resulting lists -- EA