But this is not another #pragma omp parallel for. It's a parallel implementation of STL algorithms like std::sort or std::nth_element etc. - you can replace your sequential calls by multithreaded versions easily. Like the top post, I would recommend having a look at GNU's parallel mode (aka MCSTL, Multi Core STL). Peter Sanders recognized the potential of such an implementation very early, his group published the first version of MCSTL in 2006: http://algo2.iti.kit.edu/singler/mcstl/

Sadly, it looks like it didn't get continued by the GNU folks after they integrated it. It still exists, though.