Boost C++ Libraries

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

Next

Boost.Sort

Steven Ross

Francisco Tapia

Orson Peters

Distributed under the Boost Software License, Version 1.0.

Table of Contents

1.- Introduction
2.- Single Thread Algorithms
2.0.- Overview
2.1.-Spreadsort
Overview
Introduction
Overloading
Performance
Tuning
Spreadsort
Header <boost/sort/spreadsort/spreadsort.hpp>
Integer Sort
Float Sort
String Sort
Rationale
Definitions
Frequently Asked Questions
Acknowledgements
Bibliography
History
Boost.Sort C++ Reference
Header <boost/sort/pdqsort/pdqsort.hpp>
Header <boost/sort/spreadsort/float_sort.hpp>
Header <boost/sort/spreadsort/integer_sort.hpp>
Header <boost/sort/spreadsort/spreadsort.hpp>
Header <boost/sort/spreadsort/string_sort.hpp>
2.2.- pdqsort
Introduction
Usage
Benchmark
The Best Case
The Average Case
The Worst Case
Bad Partitions
2.3.- spinsort
Description
Benchmark
Programming
2.4.- flat_stable_sort
Description
Benchmark
Programming
2.5.- Linux Benchmarks
Near Sorted Data
Complex (Several Types)
2.6.- Windows Benchmarks
Near Sorted Data
Complex (Several Types)
3.- Parallel Algorithms
3.1- block_indirect_sort
Description
Benchmark
Programming
Internal Description
Design Process
3.2.- Sample_Sort
Description
Programming
3.3.- Parallel_stable_sort
Description
Programming
3.4- Linux Benchmarks
3.5- Windows Benchmark
4.- Bibliography
5.- Gratitude

The goal of the Boost Sort Library is provide to the users, the most modern, fast, and memory-efficient sorting algorithms.

This library provides stable and unstable sorting algorithms, in single threaded and parallel versions.

These algorithms do not use any other library or utility, you only need to include boost/sort/sort.hpp or one of the more specific headers. The parallel algorithms need a C++11 compliant compiler.

Single Thread Algorithms

                  |       |                            |                                            | Comparison          |
Algorithm         |Stable |   Additional memory        |Best, average, and worst case               | method              |
------------------+-------+----------------------------+--------------------------------------------+---------------------+
spreadsort        |  no   |      key_length            | N, N sqrt(LogN), min(N logN, N key_length) | Hybrid radix sort   |
pdqsort           |  no   |      Log N                 | N, N LogN, N LogN                          | Comparison operator |
spinsort          |  yes  |      N / 2                 | N, N LogN, N LogN                          | Comparison operator |
flat_stable_sort  |  yes  |size of the data / 256 + 8K | N, N LogN, N LogN                          | Comparison operator |
                  |       |                            |                                            |                     |

  • spreadsort is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross.
  • pdqsort is a improvement of the quick sort algorithm, designed and developed by Orson Peters.
  • spinsort is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia.
  • flat_stable_sort is a stable sort that uses very little additional memory (around 1% of the size of the data), providing 80% - 90% of the speed of spinsort, designed and developed by Francisco Tapia.
Parallel Algorithms

                      |       |                        |                              |
Algorithm             |Stable |   Additional memory    |Best, average, and worst case |
----------------------+-------+------------------------+------------------------------+
block_indirect_sort   |  no   |block_size * num_threads| N, N LogN , N LogN           |
sample_sort           |  yes  |        N               | N, N LogN , N LogN           |
parallel_stable_sort  |  yes  |      N / 2             | N, N LogN , N LogN           |
                      |       |                        |                              |

  • Sample_sort is a implementation of the Samplesort algorithm done by Francisco Tapia.
  • Parallel_stable_sort is based on the samplesort algorithm, but using a half of the memory used by sample_sort, conceived and implemented by Francisco Tapia.
  • Block_indirect_sort is a novel high-speed parallel sort algorithm with low additional memory consumption, conceived and implemented by Francisco Tapia.

The block_size is an internal parameter of the algorithm, which in order to achieve the highest speed, changes according to the size of the objects to sort according to the next table. The strings use a block_size of 128.

                                |        |         |         |         |         |         |          |
object size (bytes)             | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 -    |
--------------------------------+--------+---------+---------+---------+---------+---------+----------+
block_size (number of elements) |  4096  |  2048   |   1024  |   768   |   512   |   256   |  128     |
                                |        |         |         |         |         |         |          |


Next