Re: [boost] [review] Formal review period for Sort library continuing through November 19

Steven Ross wrote:

On Mon, Nov 17, 2014 at 7:21 AM, Phil Endecott wrote:

...

Steven Ross wrote:

...

If std::sort can sort it, so can string_sort if you use the available functors properly.

How about:

bool compare_distance_from_origin(point& a, point& b) { return sqr(a.x)+sqr(a.y) < sqr(b.x)+sqr(b.y); }

std::sort(points.begin(),points.end(),&compare_distance_from_origin);

Your radix key is: sqr(x) + sqr(y). If you make all your functors work relative to that generated key, it'll work fine.

So my thought was, you wouldn't want to do that because all that extra maths is being done so frequently and the performance would be considerably worse than std::sort. But:

I think many people are confused about the limitations of radix sorts, because LSD radix sorting over more complex variable-length keys is inefficient, but MSD radix sort does well with variable-length keys.

Ah, that may be true; I was overlooking the fact that not every bit of the value is looked at if the values are sufficiently well separated. Regards, Phil.