Parallel Sort

Table of Contents

• Include the Header
• Sort a Range of Items
• Sort a Range of Items with a Custom Comparator
• Enable Stateful Data Passing

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>

Sort a Range of Items

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()));

Note

Elements are compared using the operator <.

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>{}));

Note

tf::Taskflow::sort is not stable. That is, two or more objects with equal keys may not appear in the same order before sorting.

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()));