docs/ParallelSort.html
| | Taskflow: A General-purpose Task-parallel Programming System |
Loading...
Searching...
No Matches
Parallel Sort
Taskflow provides template functions for constructing tasks to sort ranges of items in parallel.
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) sorts the range [first, last) in ascending order using a parallel divide-and-conquer algorithm built on top of introductory sort (introsort). Taskflow recursively splits the range into sub-ranges, sorts each sub-range in parallel across available workers, and merges the sorted sub-ranges back into a fully sorted result. The following diagram illustrates this process on eight elements:
The dashed edges show the recursive splitting phase; the green edges show per-subrange sequential sort at the base case; the orange edges show the parallel merge phase that reconstructs the fully sorted sequence. To correctly use tf::Taskflow::sort, the given iterators must be random-accessible. The following example creates a task that sorts a vector in ascending 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()));
class to create an executor
Definition executor.hpp:62
tf::Future< void > run(Taskflow &taskflow)
runs a taskflow once
Task sort(B first, E last, C cmp)
constructs a dynamic task to perform STL-styled parallel sort
class to create a task handle over a taskflow node
Definition task.hpp:569
class to create a taskflow object
Definition taskflow.hpp:64
By default, elements are compared using the operator "<" during the sorting process.
Notetf::Taskflow::sort is not a stable sorter. Elements that compare equal may appear in any order in the sorted output.
You can pass iterators by reference using std::ref to marshal parameter updates between dependent tasks. This is useful when the range is not known at task-graph construction time but is initialized by an upstream task.
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));
// wrong! first and last are captured by copy at construction time
// tf::Task sort = taskflow.sort(first, last);
init.precede(sort);
executor.run(taskflow).wait();
assert(std::is_sorted(data.begin(), data.end()));
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1571
Task & precede(Ts &&... tasks)
adds precedence links from this to other tasks
Definition task.hpp:1258
When init finishes, first and last point to the initialized data range of data, and the sort task performs parallel sort over all elements.
tf::Taskflow::sort(B first, E last, C cmp) is an overload of parallel sort that accepts a custom comparator cmp. The following example sorts a vector of integers in descending 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>{}));
A custom comparator is especially useful when sorting a range of objects whose natural ordering is not defined by the operator "<". For example, user-defined structs or classes that must be ordered by a specific field. The following example defines a Student struct and sorts a vector of students by GPA in descending order:
struct Student {
std::string name;
double gpa;
};
tf::Taskflow taskflow;
tf::Executor executor;
std::vector<Student> students = {
{"Alice", 3.8},
{"Bob", 3.5},
{"Charlie", 3.9},
{"Diana", 3.7}
};
taskflow.sort(students.begin(), students.end(),
[](const Student& a, const Student& b) {
return a.gpa > b.gpa; // descending GPA
}
);
executor.run(taskflow).wait();
// students are now ordered by descending GPA: Charlie, Alice, Diana, Bob
assert(students[0].name == "Charlie");
assert(students[1].name == "Alice");
assert(std::is_sorted(students.begin(), students.end(),
[](const Student& a, const Student& b) { return a.gpa > b.gpa; }
));