I never had any problems regarding this issue. What might be a solution is to use earplugs. A colleague of mine uses earplugs when he is doing "serious" work (as he says) and he seems to do just fine. It's just a little bit funny that you have to ask him everything twice, as he won't hear it the first time and first has to remove the earplugs -- ad you don't know beforehand if he is currently wearing his earplugs as you can't see them (at least not from two meters away). The earplugs have the psychological advantage of making other people disrupt you less often: It takes some time till you remove the earplugs and they have to ask their question twice, so they think twice if the effort of this is worth the answer -- Dummy-questions good-bye!
I have to agree; yet parallel or (at least) multi-threaded algorithms haven't made it into standard libraries. An extreme example is the Standard C library qsort(3): There are multi-threaded versions of it available http://libmt.sourceforge.net/ but not included in the base libraries. And the glibc is imho a integral part of Linux. I don't know exactly about Windows, but I assume the standard sorting function to be a serial one, too.