parallel_sort Template Function


Sort a sequence.


#include "tbb/parallel_sort.h"


template<typename RandomAccessIterator> 
void parallel_sort( RandomAccessIterator begin, RandomAccessIterator end );

template<typename RandomAccessIterator, typename Compare>
void parallel_sort( RandomAccessIterator begin, 
                   RandomAccessIterator end, 
                   const Compare& comp );

template<typename Container>
void parallel_sort( Container c );

template<typename Container>
void parallel_sort( Container c, const Compare& comp );


Performs an unstable sort of a sequence or a container. An unstable sort 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. Specifically, RandomAccessIterator must be a random access iterator, and its value type T must model the requirements in the table below.

Requirements on Value Type T of RandomAccessIterator for parallel_sort



void swap( T& x, T& y )

Swap x and y .

bool Compare::operator()( const T& x, const T& y )

True if x comes before y ; false otherwise.

A call parallel_sort(begin,end,comp) sorts the sequence [begin,end) using the argument comp to determine relative orderings. If comp(x,y) returns true then x appears before y in the sorted sequence.

A call parallel_sort(begin,end) is equivalent to parallel_sort(begin,end,std::less<T>).

A call parallel_sort(c[,comp]) is equivalent to parallel_sort(std::begin(c),std::end(c)[,comp]).


parallel_sort is comparison sort with an average time complexity of O(N log (N)), where N is the number of elements in the sequence. When worker threads are available, parallel_sort creates subtasks that may be executed concurrently, leading to improved execution times.


The following example shows various forms of parallel_sort. Arrays a and c are sorted using the default comparison, which sorts in ascending order. Arrays b and d are sorted in descending order by using std::greater<float> for comparison.

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

using namespace tbb;

const int N = 100000;
float a[N], b[N], c[N], d[N];

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

See Also