Can I parallelize sort?

As of coreutils 8.6 (2010-10-15), GNU sort already sorts in parallel to make use of several processors where available. So, it cannot be further improved in that regard like pigz or pbzip2 improve gzip or bzip2.

If your sort is not parallel, you can try and install the GNU sort from the latest version of GNU coreutils.

With GNU sort, you can limit the number of threads with the --parallel option.

The one thing that always helps me most with sort is giving it as much memory as possible, so as to reduce swapping, e.g.:

sort -S 20G

If your file is large enough, sorting will cause disk swapping, either because the allocated virtual memory is growing too big, or because the sort program itself is swapping chunks to disk and back. Older sort implementations are more likely to have this "sort via disk buffer" sort of behavior, since it was the only way to sort large files in the old days.

sort has a -m option that may help you here. It might be faster to split the file into chunks — say with split -l — sort them independently, then merge them back together.

Then again, it may be that this is exactly what "sort via disk buffer" does. The only way to find out if it helps is to benchmark it on your particular test load. The critical parameter will be the line count you give to split -l.