Intel Threading Building Blocks

parallel_sort

parallel_sort is a comparison sort with an average time complexity O(nlogn). When worker threads are available, parallel_sort creates subtasks that may be executed concurrently. This sort provides an unstable sort of the sequence [begin1, end1). Being an unstable sort means that it might not preserve the relative ordering of elements with equal keys.

The sort is deterministic; sorting the same sequence will produce the same result each time. The requirements on the iterator and sequence are the same as for std::sort.

A call to parallel_sort(i,j,comp) sorts the sequence [i,j) using the third argument comp to determine relative orderings. If comp(x,y) returns true, x appears before y in the sorted sequence. A call to parallel_sort(i,j) is equivalent to parallel_ sort(i,j,std::less<T>).

Example 4-9 shows two sorts. The sort of array a uses the default comparison, which sorts in ascending order. The sort of array b sorts in descending order by using std:: greater<float> for comparison.

Example 4-9. Two sorts

#include "tbb/parallel_sort.h"
#include <math.h>

using namespace tbb;

const int N = 100000;
float a[N];
float b[N];

void SortExample( ) {
    for( int i = 0; i < N; i++ ) {
       a[i] = sin((double)i);
       b[i] = cos((double)i);
    }
    parallel_sort(a, a + N);
    parallel_sort(b, b + N, std::greater<float>( ));
}