[sort::parallel] (https://github.com/fjtapia/sort_parallel)

• In this parallel library, you can find stable and not stable sort algorithms, in a single thread and parallel version, with similar performance than the provided by other libraries as TBB, Cilk, OpenMP or IPP.

• The intention is to create algorithms only with the utilities provided by C++11, without any other library. Any C++11 compliant compiler can compile and run these algorithms.

• These algorithms are generic, can sort any kind of object using a comparison object, in contrast with the specialized algorithms, as spreadsort, which only sort integers, strings and float values in a single thread version, but with a speed greater than the generic sort algorithms.

• The algorithms are exception safe, it means, the exceptions generated by the algorithms guarantee the integrity of the objects to sort, but not they relative order. If the exception is generate inside the objects (in the move or in the copy constructor..) the results can be unpredictable.

Algorithms

1. introsort

• Parallel : no
• Stable : no
• Additional Memory : Log(N)
• Best case : N Log(N)
• Average case : N Log(N)
• Worst case : N Log(N)

2. parallel_introsort

• Parallel : yes
• Stable : no
• Additional Memory : Log(N)
• Best case : N Log(N)
• Average case : N Log(N)
• Worst case : N Log(N)

3. **smart_**merge_sort

• Parallel : no
• Stable : yes
• Additional Memory : N / 2
• Best case : N Log(N)
• Average case : N Log(N)
• Worst case : N Log(N)

4. **parallel_**stable_sort

• Parallel : yes
• Stable : yes
• Additional Memory : N / 2
• Best case : N Log(N)
• Average case : N Log(N)
• Worst case : N Log(N)

5. sample_sort

• Parallel : yes
• Stable : yes
• Additional Memory : N
• Best case : N Log(N)
• Average case : N Log(N)
• Worst case : N Log(N)

Benchmarks

The speed of the algorithm over a machine depend, mainly of the algorithm, but also of the processor (speed, number of HW threads), memory and cache memory.

In the folder benchmarks, you have an easy and fast benchmark, for to check the speed of the algorithms on your computer.

There are versions for several compilers. In the folder you can find a README.txt with instructions about how to run the benchmarks.

The compilation need about 2 mins and the running about 5 mins, depending of your computer.

• GCC :GCC compiler over a Linux x64
• CLANG : CLANG compiler over a Linux x64
• VC++ : Visual C++ over a Windows

Author and Copyright

This library had been created for to be integrated in the Boost Library, inside the [boost::sort library] (http://www.boost.org/doc/libs/release/libs/sort), with the spreadsort algorithms designed and implemented by Steven Ross. It is pending of the final approval, due this, can suffer some changes until the final version and definitive approval in the Boost Library. You can find in [https://github.com/fjtapia/sort_parallel] (https://github.com/fjtapia/sort_parallel)

Copyright 2015 [Francisco Tapia ([email protected]) ] (mail:[email protected]). Distributed under the Boost Software License, Version 1.0. (See http://www.boost.org/LICENSE_1_0.txt)

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

Installation

• This library is include only.
• Don't need to link with any static or dynamic library.
• Don't have any dependence of any other Boost or external libraries.
• For to use, only need a to include the files of the boost/sort/parallel folder, any more.
• This library had been compiled successfully with the next compilers : GCC 4.7, GCC 4.8, GCC 4.9 , CLANG 3.6, Visual C++ 2013 Update 4, Visual C++ 2015

---

Copyright 2015 [Francisco Tapia ([email protected]) ] (mail:[email protected])