parallel_sort Template Function

Summary

Sort a sequence.

Header

#include "tbb/parallel_sort.h"

Syntax

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

Description

Performs an unstable sort of sequence [begin1, end1). 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

Pseudo-Signature

Semantics

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(i,j,comp) sorts the sequence [i,j) 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(i,j) is equivalent to parallel_sort(i,j,std::less<T>).

Complexity

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.

Example

The following example 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.

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

See Also