How about this: [...] The calls and overloads for my suggestion would be: flex_sort(first, last) flex_sort(first, last, compare) flex_sort(first, last, compare, swap)
Exactly what I had in mind, except I was more thinking about something like template < typename Iterator, typename Compare, int SmallThreshold, int DepthFallback, typename MainSort, typename FallbackSort, typename Swapper
void flex_sort(Iterator first, Iterator last, Compare compare) Mainsort would be something like Template <typename Iterator, typename Compare, typename Swapper> struct { size_t distance(Iterator first, Iterator last); // finds pivot & partition Iterator split(Iterator first, Iterator last); }; And all MainSort and FallbackSort would share some traits and tell what kind of iterator they need (to have static assertions and stuff, at compile time you would know that you're trying to use a sort algorithm that's inefficient for the iterators you have). Swapper would be struct { Element get_elem(Iterator i); void operator()(Iterator left, Iterator right); }; So basically flex_sort would be something like (typing as I think, not valid C++): void flex_sort(Iterator first, Iterator last, Compare compare, int depth = 0) { if (depth >= DepthFallBack) { FallbackSort<...>(compare, swapper)(first, last); } else { Iterator pivot = MainSort<...>(compare, swapper).split(first, last); // pivot => last we didn't split but sort the stuff (means the data was too small to be split) if (pivot != last) { ++depth; flex_sort(first, pivot, compare, depth); advance(pivot, 1); flex_sort(pivot, last, compare, depth); } } } For quicksort, split would be: void MainSort::split(first, last) { Iterator pivot = last; if (distance(first, last) > threshold) { pivot = find_pivot(first, last); Iterator start = first; advance(start, 1); pivot = partition (start, last, std::bind2nd(compare, swapper.get_elem(pivot))); swapper(pivot, first); } else { insert_sort(first, last... ?); } return pivot; } What do you think? -- EA