Internal memory sorting is implemented in parallel_sort.h as a parallel quick sort with a sequential partition step.
The implementation uses the TPIE job manager, implemented in job.h and job.cpp.
Like std::sort, the input to parallel sorting is given as two forward iterators, begin
and end
. It is then up to the implementation to spawn as many quick sort jobs as needed. If the input is sufficiently small, std::sort
is used directly. Otherwise, the input is repeatedly partitioned (using a sequential partition), and a new job is spawned on the smaller half of the result from the partition. When the job size is sufficiently small, std::sort
is used.
Example sorting.cpp:
Place in your tpie
project folder, and on Linux, compile with: