Bucket Sort.  Bucket Sort is faster than n lg n most of the time.  This is a technique for sorting floating point numbers rather than integers.  You could modify this to sort strings as well (sort of).

The trick is we make the assumption that the data is evenly distributed over the range.

"Evenly distributed" is that if you look at any fraction of the range (p/q).  Then that subrange should contain p/q of the elements.

The Bucket Sort is surprisingly simple:

If I have n floating point numbers in the range [f...l], I divide the range into n equal subranges.  [f...f + (l-f)/n], [f + (l-f)/n...f+2(l-f)/n],
[f + 2(l-f)/n...f+3(l-f)/n]...[f+(n-1)(l-f)/n...l].

If I have ten elements between 1 and 2, then I'd divide the range into
[1...1.1],[1.1...1.2],[1.2...1.3],...[1.9...2].

Then I go through my array one at a time, and place each point into a data structure (array, linked list, whatever) corresponding to the subrange that that particular point is.

Then I sort each of those data structures, which are expected to have one element each.  And then I paste these data structures together.  The stuff in the first range has to come first, then the stuff in the second range, and so forth.

So, if I'm sorting 1.05, 1.75, 1.95, 1.35, 1.65, 1.85, 1.25, 1.45, 1.55, 1.15).  They will get arranged into bins:
1.05   1.15   1.25   1.35   1.45   1.55   1.65   1.75    1.85    1.95

Each of these bins has one element so sorting takes very little time.
Copy the contents of the bins into the original array.

Knowing which bin (or bucket) a point goes into is simply a little bit of arithmetic:  (p-min)/bucketsize, rounded down.

If the data is evenly distributed, this algorithm runs in Th(n) time.

The moral of the story:

You cannot beat n lg n time for sorting data UNLESS you can exploit an assumption about the data that proves true.

1.  Counting Sort:  The assumption is that the number of elements to be sorted is significantly larger than the number of possible values that these elements could have.  [In other words, we're assuming a LOT of repeats.]

2.  Radix Sort:  The assumption is the same as above, since the radix sort is the counting sort applied several times.

3.  Bucket Sort:  The assumption is that the data are evenly distributed.