[R] Ordering long vectors

[Thomas Lumley]

On Sat, 7 Jun 2003, [ISO-8859-1] Göran Broström wrote:

>
> I need to order a long vector of integers with rather few unique values.
> This is very slow:


I think the culprit is

src/main/sort.c: orderVector1

    /* Shell sort isn't stable, but it proves to be somewhat faster
       to run a final insertion sort to re-order runs of ties when
       comparison is cheap.
    */

This also explains:

> aa<-sample(rep(1:10,50000))
> system.time( order(aa, 1:length(aa)))
[1] 3.67 0.01 3.68 0.00 0.00
> system.time( order(aa))
^C
Timing stopped at: 49.33 0.01 49.34 0 0

which is perhaps the simplest work-around :).


	-thomas