Ordering long vectors

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