Intel Threading Building Blocks

Name

parallel_sort<RandomAccessIterator, Compare> Template Function — Sorts a sequence.

Synopsis

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

Description

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

Table 4-2. Requirements on value type T of RandomAccessIterator for parallel_sort

Pseudosignature	Semantics
void swap(T&x,T&y)	Swaps x and y.
boolCompare::operator()(constT&x,constT&y)	True if x comes before y; false otherwise.

Complexity

parallel_sort is a comparison sort with an average time complexity of O(nlogn)on a single-processor core, where n is the number of elements in the sequence. Complexity reduces to O(N) as the number of processors increases. When worker threads are available, parallel_sort creates subtasks that may be executed concurrently, leading to improved execution times.