[R] x[order(x)] vs sort(x)?

[Prof Brian Ripley]

On Thu, 21 Aug 2008, Rory.WINSTON at rbs.com wrote:

> Hi
>
> I have a question (which may be an obvious one). It is about an idiom 
> which I have seen quite often:
>
> o <- order(x); <- x[o]
>
> vs. the alternative
>
> x <- sort(x)
>
> I am just wondering as to the rationale behind the order/reindex idiom vs sorting. Especially as there seems to be a marked performance difference (especially for integer vectors):
>
>> x <- trunc(runif(1E6, 1, 100))

Those are doubles, BTW.

>> system.time(y <- x[order(x)])
>   user  system elapsed
>   1.19    0.01    1.21
>> system.time(y <- sort(x))
>   user  system elapsed
>   0.22    0.00    0.22
>
> I suspect that the propensity for the order/reindex idiom may be related 
> to memory or space performance then, rather than time? Can anyone 
> confirm if this is the case?

You don't give any examples of where you have seen the idiom, so leave us 
to guess.

order() is usually used when it is needed for other objects: even for 
sort() this applies to the names.  And x[o] is used to preserve classes, 
for example: look at the code of sort.default.  And sort.list has a method 
for radix sorting ideally suited to your example.

There are faster options for sort, too.

On my system
> x <- trunc(runif(1E6, 1, 100))
> system.time(y <- x[order(x)])
    user  system elapsed
   1.128   0.010   1.471
> system.time(y <- sort(x))
    user  system elapsed
   0.138   0.005   0.259
> system.time(y <- sort.int(x, method="quick"))
    user  system elapsed
   0.073   0.000   0.132
> x <- as.integer(x)
> system.time(y <- x[sort.list(x, method="radix")])
    user  system elapsed
   0.033   0.001   0.053
> names(x) <- 1:1e6
> system.time(y <- sort(x))
    user  system elapsed
   0.715   0.023   1.475
> system.time(y <- sort.int(x, method="quick"))
    user  system elapsed
   1.519   0.015   3.077
> system.time(y <- x[sort.list(x, method="radix")])
    user  system elapsed
   0.138   0.000   0.287



-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595