Boost C++ Libraries 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.

3.2.- Sample_Sort

This is a implementation of the Samplesort algorithm by Francisco Tapia for the Boost Library.

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

The additional memory needed is of the same size than the data

                      |       |                        |                              |
Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
sample_sort           |  yes  |        N               |     N, N LogN , N LogN       |
                      |       |                        |                              |

You can see their performance in the Benchmarks chapter