Шаблон класса для блочной сортировки

template<class T>
struct Basket
{
    std::list<T> m_listElements;
    long m_lDistance;
    Basket(long lDistance)
       : m_lDistance(lDistance)
    {  }
};
template<class T, class LengthTraits = LengthTraitsTmpl<T> >
struct A
{
    T m_vFirst; // Начало отсчёта
    std::list<Basket> listBaskets; /* список корзин. списков можно завести 2 - в зависимости от знака
                                                смещения от начала отсчёта. А можно просто при каждой вставке 
                                                (если нужно) перемещать начало отсчёта таким образом, 
                                                чтобы все смещения были положительные */
   void insert(const T& v)
   {
       long lDistance = LengthTraits::GetDistance(m_vFirst, v);
       for(std::list<Basket>::iterator it = listBaskets.begin(); it != listBaskets.end(); ++it)
       {
            if(it->m_lDistance == lDistance)
            {
                it->m_listElements.push_back(v);
                break;
            }
            if(it->m_lDistance > lDistance)
            {
                // Заводим новую корзину
                Basket basket(lDistance);
                basket.push_back(v);
                listBaskets.insert_before(it, basket);
                break;
            }
       }
   }
};
 
template<class T>
struct LengthTraitsTmpl
{
     long GetDistance(const T& f, const T& v);
};
 
// Теперь пишем специализации для необходимых типов:
 
// для целого
template<>
struct LengthTraitsTmpl<int>
{
     static long GetDistance(const int& f, const int& v)
     {
          return (v - f) / 10; // Например по 10 элементов в корзине
     }
};
 
// для строки
template<>
struct LengthTraitsTmpl<std::string>
{
     static long GetDistance(const std::string& f, const std::string& v)
     {
          // строки можно попробовать распихать по корзинам в виде алфавита
          // это только пример, потому что здесь необходимо вывести формулу
          // для номера корзины в зависимости от индекса символа в строке.
          return v[0] - f[0];
     }
};
 ну и так далее...