Taskflow Algorithms » Parallel Sort

Taskflow provides template functions for constructing tasks to sort ranges of items in parallel.

Include the Header

You need to include the header file, taskflow/algorithm/sort.hpp, for creating a parallel-sort task.

#include <taskflow/algorithm/sort.hpp>

The task created by tf::Taskflow::sort(B first, E last) performs parallel sort to rank a range of elements specified by [first, last) in increasing order. The given iterators must be random-accessible. The following example creates a task to sort a data vector in increasing order.

tf::Taskflow taskflow;
tf::Executor executor;

std::vector<int> data = {1, 4, 9, 2, 3, 11, -8};

tf::Task sort = taskflow.sort(data.begin(), data.end());

executor.run(taskflow).wait();

assert(std::is_sorted(data.begin(), data.end()));

Sort a Range of Items with a Custom Comparator

tf::Taskflow::sort(B first, E last, C cmp) is an overload of parallel sort that allows users to specify a custom comparator. The following example sorts a data vector in decreasing order.

tf::Taskflow taskflow;
tf::Executor executor;

std::vector<int> data = {1, 4, 9, 2, 3, 11, -8};

tf::Task sort = taskflow.sort(data.begin(), data.end(), 
  [](int a, int b) { return a > b; }
);

executor.run(taskflow).wait();

assert(std::is_sorted(data.begin(), data.end(), std::greater<int>{}));

Enable Stateful Data Passing

The iterators taken by tf::Taskflow::sort are templated. You can use std::reference_wrapper to enable stateful data passing between the sort task and others. The following example creates a task init to initialize the data vector and a task sort to sort the data in parallel after init finishes.

tf::Taskflow taskflow;
tf::Executor executor;

std::vector<int> data;
std::vector<int>::iterator first, last;

tf::Task init = taskflow.emplace([&](){ 
  data  = {1, 4, 9, 2, 3, 11, -8}; 
  first = data.begin();
  last  = data.end();
});
tf::Task sort = taskflow.sort(
  std::ref(first), std::ref(last), [] (int l, int r) { return l < r; }
);
init.precede(sort);

executor.run(taskflow).wait();

assert(std::is_sorted(data.begin(), data.end()));