1[/=========================================================================== 2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters 3 4 5 Distributed under the Boost Software License, Version 1.0 6 See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt 8=============================================================================/] 9 10[section:sample_sort 3.2.- Sample_Sort] 11 12[: 13This is a implementation of the [*[@https://en.wikipedia.org/wiki/Samplesort Samplesort]] algorithm by Francisco Tapia for the Boost Library. 14 15It is a highly efficient [*parallel stable sort], optimized for use with many threads. 16 17The additional memory needed is of the same size than the data 18] 19 20[section:sample_description Description] 21[: 22 23[*[teletype] 24`` 25 | | | | 26 Algorithm |Stable | Additional memory |Best, average, and worst case | 27 ----------------------+-------+------------------------+------------------------------+ 28 sample_sort | yes | N | N, N LogN , N LogN | 29 | | | | 30`` 31] 32 33You can see their performance in the [*[link sort.parallel.linux_parallel Benchmarks]] chapter 34] 35[endsect] 36 37[section:sample_programming Programming] 38[: 39[h4[_Thread Specification]] 40 41[: 42This algorithm has an integer parameter indicating the *number of threads* to use in the sorting process, 43which always is the last value in the call. The default value (if left unspecified) is the number of HW threads of 44the machine where the program is running provided by std::thread::hardware_concurrency(). 45 46If the number is 1 or 0, the algorithm runs with only 1 thread. 47 48The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater 49than the number of hardware threads on the machine. We can pass 100 threads in a machine with 4 HW threads, 50and in the same mode we can pass a function as (std::thread::hardware_concurrency() / 4 ). 51If this value is 0, the program is executed with 1 thread. 52 53] 54 55[h4[_Programming]] 56[: 57You only need to include the file boost/sort/sort.hpp. 58 59The algorithm run in the namespace boost::sort 60 61[c++] 62`` 63 #include <boost/sort/sort.hpp> 64 65 66 template <class iter_t> 67 void sample_sort (iter_t first, iter_t last); 68 69 template <class iter_t, typename compare> 70 void sample_sort (iter_t first, iter_t last, compare comp); 71 72 template <class iter_t> 73 void sample_sort (iter_t first, iter_t last, uint32_t num_thread); 74 75 template <class iter_t, typename compare> 76 void sample_sort (iter_t first, iter_t last, compare comp, uint32_t num_thread); 77 78`` 79 80This algorithm needs a *C++11 compliant compiler*, and doesn't need any other code or library. Correct operation is not guaranteed with older compilers. 81 82If the number of threads is unspecified, this uses the result of std::thread::hardware_concurrency(). 83 84This algorithm uses a *comparison object*, in the same way as the standard library sort 85algorithms. If not defined, the comparison object is std::less, which uses 86the < operator internally. 87 88This algorithm is [*exception safe], meaning that, the exceptions generated by the algorithm 89guarantee the integrity of the objects to sort, but not their relative order. If the exception 90is generated inside the objects (in the move or in the copy constructor.. ) the results can be 91unpredictable. 92] 93] 94[endsect] 95 96[endsect] 97 98 99 100