Internal sorting

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:

#include <tpie/tpie.h> // for tpie::tpie_init
#include <boost/random.hpp> // for boost::mt19937
#include <vector> // for std::vector
#include <algorithm> // for std::generate
#include <tpie/parallel_sort.h> // for tpie::parallel_sort

int main() {
    tpie::tpie_init();
    boost::mt19937 rng;
    std::vector<int> numbers(1 << 29);
    std::generate(numbers.begin(), numbers.end(), rng);
    tpie::parallel_sort(numbers.begin(), numbers.end(), std::less<int>());
    tpie::tpie_finish();
    return 0;
}

Place in your tpie project folder, and on Linux, compile with:

$ g++ -I. -Ibuild -c sorting.cpp -Wall -Wextra -O3
$ g++ sorting.o -o sorting build/tpie/libtpie.a -lboost_date_time-mt -lboost_thread-mt -lboost_filesystem-mt -lboost_system-mt