It just occurred to me that even if the key size of unreasonably large, you might still devise a O(n) sorting algorithm with hashing. Just hash each value and record the number of occurrences as per counting sort. But then you need a way to visit the hash table in a sorted fashion. You'd need a hash algorithm that inserted the values sorted, which is problematic as that's the very problem we're attempting to solve!However if your hash algorithm was just key MOD tableSize then you could lower the space required to a fixed multiple of the number of values, instead of a multiple of the key size, which may be prohibitive. This would multiply the time complexity by a factor of keySize / tableSize however, resulting in a very clear trade-off. You can sacrifice time complexity for storage space, or vice versa.

But suppose you run the values through a standard hash function, counted each occurrence, and then ran an introsort on the hash table itself. You'd be doing a O(nlogn) sort with respect to the number of *distinct* values. Dpending on the data set, this might yield amazing performance.

Just something to consider

But suppose you run the values through a standard hash function, counted each occurrence, and then ran an introsort on the hash table itself. You'd be doing a O(nlogn) sort with respect to the number of *distinct* values. Dpending on the data set, this might yield amazing performance.

Mergesort.