C++ parallel sort

Parallel sorting is part of C++17

Implementation-wise, everything has aligned as of Ubuntu 19.10, where you can do just:

#include <execution>
#include <algorithm>

std::sort(std::execution::par_unseq, input.begin(), input.end());

and build and run with:

sudo apt install gcc libtbb-dev
g++ -ggdb3 -O3 -std=c++17 -Wall -Wextra -pedantic -o main.out main.cpp -ltbb
./main.out

That function call automatically spawns threads for you that do the parallel sort.

Further details at: Are C++17 Parallel Algorithms implemented already?

For an algorithm discussion, see: Which parallel sorting algorithm has the best average case performance?

If you are using libstdc++ (g++'s standard) as your standard library implementation, you can rely on its built in "Parallel Mode".

To use it, you need to compile with -fopenmp and have _GLIBCXX_PARALLEL defined during compilation. Here you can find more information on the usage as well as a list of the algorithms that gcc will consider for parallization.

Be aware of the following warning from the usage site:

Note that the _GLIBCXX_PARALLEL define may change the sizes and behavior of standard class templates such as std::search, and therefore one can only link code compiled with parallel mode and code compiled without parallel mode if no instantiation of a container is passed between the two translation units. Parallel mode functionality has distinct linkage, and cannot be confused with normal mode symbols.

Each individual parallel algorithm can also be called explicitly. You only need to compile with -fopenmp (and not the _GLIBCXX_PARALLEL flag), and include the parallel/numeric or parallel/algorithm depending on the function listed in this subsection of the documentation. Be aware that the parallel algorithms are in the __gnu_parallel namespace.