Bug 15644 - sort.list(...,method="radix") can support negatives easily
Summary: sort.list(...,method="radix") can support negatives easily
Status: CLOSED FIXED
Alias: None
Product: R
Classification: Unclassified
Component: Wishlist (show other bugs)
Version: R 3.0.2
Hardware: All All
: P5 enhancement
Assignee: R-core
URL:
Depends on:
Blocks:
 
Reported: 2014-01-20 16:51 UTC by Matt Dowle
Modified: 2014-03-05 11:01 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Matt Dowle 2014-01-20 16:51:17 UTC
do_radixsort() in src/main/sort.c contains the following line :

    if(tmp < 0) error(_("negative value in 'x'"));

This wish is to remove that line.  The function already supports negatives with no other changes needed, iiuc.

It implements a counting sort. First the range [xmin,xmax] is found. If that range spans negative numbers, it would be fine. If that range is entirely over negatives, that's also fine. It's the width of the range (i.e. xmax-xmin) that is very reasonably restricted to 100,000. Later in the function, 'off' is calculated to shift the range to start from 0 (or 1 depending on napos) in order to index the counts vector. That shift can be done on a range that spans negatives just as well as a range that spans positives only.

I can't think of any stability concerns because ties in negatives would be treated just the same as ties in positives.

IIUC !?

So the wish is to remove the one line highlighted above.

The manual ?sort.sort contains :
   "Method "radix" is only implemented for integer x with a range of
    less than 100,000."
It doesn't mention there that negatives are disallowed. Therefore, changing the code to allow negatives may be considered closer to the documented behaviour.

I can't think of any downside to the change.