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

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Edouard A. (edouard_at_[hidden])
Date: 2009-05-09 14:20:20

> 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