| 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.

# 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) 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()));
tf::Executor
class to create an executor
Definition executor.hpp:62
tf::Executor::run
tf::Future< void > run(Taskflow &taskflow)
runs a taskflow once
tf::FlowBuilder::sort
Task sort(B first, E last, C cmp)
constructs a dynamic task to perform STL-styled parallel sort
tf::Task
class to create a task handle over a taskflow node
Definition task.hpp:569
tf::Taskflow
class to create a taskflow object
Definition taskflow.hpp:64

By default, elements are compared using the operator "<" during the sorting process.

Note
  tf::Taskflow::sort is not a stable sorter. Elements that compare equal may appear in any order in the sorted output.

## Capture Iterators by Reference

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()));
tf::FlowBuilder::emplace
Task emplace(C &&callable)
creates a static task
Definition flow_builder.hpp:1571
tf::Task::precede
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.

# Sort with a Custom Comparator

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