That's about 200KB/s. Pretty crap.
I presume you're thrashing swap?

One thing to check is if you don't need multibyte sorting,
then prepend the sort command with LANG=C

Sounds like you need a database (indexes) to be honest.

If the output is a small % of the input, then
explicitly partitioning the input would be beneficial.
I.E.: while sort -u chunk | sort -u