EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/sort/doc/sample_sort.qbk

[/===========================================================================
 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters


 Distributed under the Boost Software License, Version 1.0
 See accompanying file LICENSE_1_0.txt or copy at
 http://www.boost.org/LICENSE_1_0.txt
=============================================================================/]

[section:sample_sort 3.2.- Sample_Sort]

[:
This is a implementation of the [*[@https://en.wikipedia.org/wiki/Samplesort 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
]

[section:sample_description Description]
[:

[*[teletype]
``
                          |       |                        |                              |
    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 [*[link sort.parallel.linux_parallel Benchmarks]] chapter
]
[endsect]

[section:sample_programming Programming]
[:
[h4[_Thread Specification]]

[:
This algorithm has an integer parameter indicating the *number of threads* to use in the sorting process,
which always is the last value in the call. The default value (if left unspecified) is the number of HW threads of
the machine where the program is running provided by std::thread::hardware_concurrency().

If the number is 1 or 0, the algorithm runs with only 1 thread.

The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater
than the number of hardware threads on the machine. We can pass 100 threads in a machine with 4 HW threads,
and in the same mode we can pass a function as (std::thread::hardware_concurrency() / 4 ).
If this value is 0, the program is executed with 1 thread.

]

[h4[_Programming]]
[:
You only need to include the file boost/sort/sort.hpp.

The algorithm run in the namespace boost::sort

[c++]
``
    #include <boost/sort/sort.hpp>


    template <class iter_t>
    void sample_sort (iter_t first, iter_t last);

    template <class iter_t,  typename compare>
    void sample_sort (iter_t first, iter_t last, compare comp);

    template <class iter_t>
    void sample_sort (iter_t first, iter_t last, uint32_t num_thread);

    template <class iter_t,  typename compare>
    void sample_sort (iter_t first, iter_t last, compare comp, uint32_t num_thread);

``

This algorithm needs a *C++11 compliant compiler*, and doesn't need any other code or library. Correct operation is not guaranteed with older compilers.

If the number of threads is unspecified, this uses the result of std::thread::hardware_concurrency().

This algorithm uses a *comparison object*, in the same way as the standard library sort
algorithms. If not defined, the comparison object is std::less, which uses
the < operator internally.

This algorithm is [*exception safe],  meaning that, the exceptions generated by the algorithm
guarantee the integrity of the objects to sort, but not their relative order. If the exception
is generated inside the objects (in the move or in the copy constructor.. ) the results can be
unpredictable.
]
]
[endsect]

[endsect]