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:

This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.

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

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

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

Taskflow: A General-purpose Task-parallel Programming System: Parallel Sort

Table of Contents

Include the Header

Sort a Range of Items

Capture Iterators by Reference

Sort with a Custom Comparator