Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

3.3.- Parallel_stable_sort

This is an adaptation of the Samplesort algorithm, using an additional memory a half of the memory used by the data (the original algorithm uses an additional memory as the used by the data).

It is a highly efficient parallel stable sort, optimized for use with many threads.

                      |       |                        |                              |
Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
----------------------+-------+------------------------+------------------------------+
parallel_stable_sort  |  yes  |        N / 2           |     N, N LogN , N LogN       |
                      |       |                        |                              |

You can see their performance in the Benchmarks chapter


PrevUpHomeNext