EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/sort/doc/parallel_stable_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:parallel_stable_sort 3.3.- Parallel_stable_sort]
[section:parallel_description Description]
[:
This is an adaptation of the [*[@https://en.wikipedia.org/wiki/Samplesort 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.



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

[section:parallel_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 to use this code.

This algorithm run in the namespace boost::sort.

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


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

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

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

    template <class iter_t,  typename compare>
    void parallel_stable_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]