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


Sorts a sequence or a container. The sort is neither stable nor deterministic: relative ordering of elements with equal keys is not preserved and not guaranteed to repeat if the same sequence is sorted again. 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