'Nother sort idea: Hash Sort

so if a hash function can distribute keys uniformly in slot space, then all we have to do is make a hash function that distributes uniformly and guarantees that the slots are in alphabetical order, then we can iterate over the slots and do compares for the ones with multiple entries in one slot. a hash function to distribute alphabetically for strings would be something like: num_slots*s[0]/256 + num_slots*s[1]/512 + num_slots*s[2]/1024 etc. of course this doesn't work very well if your strings actually have some sort of pattern to them, like for example they're readable. :p

since it's probably impossible to guarantee uniformity this way, you may want to use an n*n hash table. or perhaps an n*n*n. etc.

i guess you could say this algorithm is approximately O(n*log_256 k) where k is average element length in bytes? assuming you're not using unicode..