boost::spreadsort for std::pair Boost 1.58 has new library spreadsort, so I tried it out.
I wrote simple sample for sorting vector of pairs of int:

#include &lt;chrono&gt;
#include &lt;iomanip&gt;

#include &lt;boost/sort/sort.hpp&gt;

// based on http://www.boost.org/doc/libs/develop/libs/sort/doc/html/sort/sort_hpp/string_sort.html

struct lessthan
{
  inline bool operator()(const std::pair&lt;int, int&gt; &amp;x, const std::pair&lt;int, int&gt; &amp;y) const
  {
    return x &lt; y;
  }
};

struct bracket
{
  inline unsigned char operator()(const std::pair&lt;int, int&gt; &amp;x, size_t offset) const
  {
    if (offset &lt; sizeof(int))
      return get_char(x.first, offset);

    return get_char(x.second, offset - sizeof(int));
  }

private:
  inline unsigned char get_char(int x, size_t offset) const
  {
    static const boost::uint64_t base_mask = 0xff;

    const int bit_shift = 8 * (sizeof(int) - offset - 1);
    unsigned char result = (x &amp; (base_mask &lt;&lt; bit_shift)) &gt;&gt; bit_shift;
    if (offset == 0)
      return result ^ 128;

    return result;
  }
};


struct getsize
{
  inline size_t operator()(const std::pair&lt;int, int&gt; &amp;) const
  {
    return 2 * sizeof(int);
  }
};

bool verify_sorted(const std::vector&lt;std::pair&lt;int, int&gt;&gt; &amp; a)
{
  lessthan ls;
  for (size_t i = 0; i + 1 &lt; a.size(); i++)
  {
    if (ls(a[i + 1], a[i]))
      return false;
  }

  return true;
}

int main()
{
  std::vector&lt;std::pair&lt;int, int&gt;&gt; r;

  srand(12345);
  for (size_t i = 0; i &lt; 10000000; i++)
    r.push_back(std::make_pair(rand(), rand()));

  {
    std::vector&lt;std::pair&lt;int, int&gt;&gt; a = r;

    auto t_start = std::chrono::high_resolution_clock::now();
    std::sort(a.begin(), a.end());
    auto t_end = std::chrono::high_resolution_clock::now();

    std::cout &lt;&lt; std::fixed &lt;&lt; std::setprecision(2) &lt;&lt; "CPU time used (std::sort): "
      &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(t_end - t_start).count()
      &lt;&lt; " ms\n";

    std::cout &lt;&lt; (verify_sorted(a) ? "OK." : "FAIL!") &lt;&lt; std::endl;
  }

  {
    std::vector&lt;std::pair&lt;int, int&gt;&gt; a = r;

    auto t_start = std::chrono::high_resolution_clock::now();
    boost::sort::spreadsort::string_sort(a.begin(), a.end(), bracket(), getsize(), lessthan());
    auto t_end = std::chrono::high_resolution_clock::now();

    std::cout &lt;&lt; std::fixed &lt;&lt; std::setprecision(2) &lt;&lt; "CPU time used (boost::sort::spreadsort::string_sort): "
      &lt;&lt; std::chrono::duration&lt;double, std::milli&gt;(t_end - t_start).count()
      &lt;&lt; " ms\n";

    std::cout &lt;&lt; (verify_sorted(a) ? "OK." : "FAIL!") &lt;&lt; std::endl;
  }
}


It's faster then std::sort, but it's seems to me this implementation is to heavyweight and ugly for such a simple task.
Can anyone propose better one?
You spend a lot of lines of code trying to get the expressions lessthan(), getsize(), and bracket() to behave like plain old functions. Consider just using plain old functions, instead. For example:

static uint8_t get_char(int x, size_t offset)
{
    const int bit_shift = 8 * (sizeof(int) - offset - 1);
    uint8_t result = (x &gt;&gt; bit_shift) &amp; 0xFF;
    if (offset == 0) result ^= 128;
    return result;
}

static uint8_t bracket(const std::pair&lt;int,int&gt;&amp; x, size_t offset)
{
    if (offset &lt; sizeof(int))
      return get_char(x.first, offset);
    return get_char(x.second, offset - sizeof(int));
}

...
string_sort(a.begin(), a.end(), bracket, getsize(), lessthan());


You could also productively replace the expression getsize() with

auto getsize = [](auto){ return 2*sizeof(int); };

...
string_sort(a.begin(), a.end(), bracket, getsize, lessthan());


Finally, lessthan is equivalent to std::less&lt;std::pair&lt;int,int&gt;&gt;, so you can just write

string_sort(a.begin(), a.end(), bracket, getsize, std::less&lt;&gt;());


That's the kind of shortening you were looking for, right? :)