// bucket sort 2
// precalculates bucket sizes

template <class It>
void bucketSort2 (It begin, It end)
{
  using namespace Detail::BucketSort;
  const Index sz = std::distance (begin, end);
  if (sz < 2) return;
  
  typedef typename std::iterator_traits <It>::value_type T;
  // find min and max
  T minv, maxv;
  min_and_max (begin, end, minv, maxv);

  if (minv == maxv) return;

  // prepare buckets
  const Index bsz = 1 + sz / BucketSize <T>::value;
  const T inv = T (bsz - 1) / (maxv - minv);

  std::unique_ptr <T[]> B (new T[sz]); // temporary store
  // offset[i+1] corresponds to beginning of the i-th bucket
  // pos[i] corresponds current writing position (size) of i-th bucket
  std::unique_ptr <Index[]> offset (new Index[bsz + 1]),
                                     pos (new Index[bsz]);

  std::fill (offset.get(), offset.get() + bsz + 1, 0);

  // calculate sizes
  for (It p = begin; p != end; ++p)
    offset[static_cast <Index> ((*p - minv) * inv) + 1]++;

  // finish offset and pos
  for (Index i = 0; i < bsz; ++i)
  {
    pos[i] = offset[i];
    offset[i + 1] += offset[i];
  }

  // scatter
  for (It p = begin; p != end; ++p)
    B[pos[static_cast <Index> ((*p - minv) * inv)]++] = *p;

  // gather
  for (Index i = 0; i < bsz; ++i)
    std::sort (B.get() + offset[i], B.get() + offset[i + 1]);

  // copy buffer back
  std::copy (B.get(), B.get() + sz, begin);
}