If it's fair for you to benchmark this, it's surely also fair for me to point out that in a lazily-evaluated language (Haskell!), Tom's approach is O(n) and equivalent to Dick's. :)
That's true if you pick the right sort algorithm. I'm not sure if it is true of whatever happens to be in Data.List; I wouldn't be surprised either way.
