1. Introduction

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.

1.1. Single Thread Algorithms

Algorithm Stable Additional memory Best case Average case Worst case Method

Spreadsort

no

key_length

\(n\)

\(n \sqrt {\log n}\)

min(\(n \log n\), N key_length)

Hybrid radix sort

pdqsort

no

\(\log n\)

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

spinsort

yes

\(n/2\)

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

flat_stable_sort

yes

size of the data / 256 + 8K

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

  • Spreadsort is an extremely fast hybrid Radix Sort algorithm, designed and developed by Steven Ross.

  • pdqsort is a improvement of Quicksort 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.

1.2. Parallel Algorithms

Algorithm Stable Additional memory Best case Average case Worst case

sample_sort

yes

\(n\)

\(n\)

\(n \log n\)

\(n \log n\)

parallel_stable_sort

yes

\(n/2\)

\(n\)

\(n \log n\)

\(n \log n\)

block_indirect_sort

no

block_size * num_threads

\(n\)

\(n \log n\)

\(n \log n\)

  • 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

2. Single Thread Algorithms

2.1. Overview

Algorithm Stable Additional memory Best case Average case Worst case Method

Spreadsort

no

key_length

\(n\)

\(n \sqrt {\log n}\)

min(\(n \log n\), N key_length)

Hybrid radix sort

pdqsort

no

\(\log n\)

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

spinsort

yes

\(n/2\)

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

flat_stable_sort

yes

size of the data / 256 + 8K

\(n\)

\(n \log n\)

\(n \log n\)

Comparison operator

  • Spreadsort is an extremely fast hybrid Radix Sort algorithm, designed and developed by Steven Ross.

  • pdqsort is a improvement of Quicksort 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.

2.2. Spreadsort

2.2.1. Introduction

Spreadsort combines generic implementations of multiple high-speed sorting algorithms that outperform those in the C++ standard in both average and worst case performance when there are over 1000 elements in the list to sort.

They fall back to std::sort on small data sets.

Warning
 These algorithms all only work on random access iterators.

They are hybrids using both radix and comparison-based sorting, specialized to sorting common data types, such as integers, floats, and strings.

These algorithms are encoded in a generic fashion and accept functors, enabling them to sort any object that can be processed like these basic data types. In the case of string_sort, this includes anything with a defined strict-weak-ordering that std::sort can sort, but writing efficient functors for some complex key types may not be worth the additional effort relative to just using std::sort, depending on how important speed is to your application. Sample usages are available in the example directory.

Unlike many radix-based algorithms, the underlying spreadsort algorithm is designed around worst-case performance. It performs better on chunky data (where it is not widely distributed), so that on real data it can perform substantially better than on random data. Conceptually, spreadsort can sort any data for which an absolute ordering can be determined, and __string_sort is sufficiently flexible that this should be possible.

Situations where __spreadsort is fastest relative to std::sort:

  • Large number of elements to sort (['N] >= 10000).

  • Slow comparison function (such as floating-point numbers on x86 processors or strings).

  • Large data elements (such as key + data sorted on a key).

  • Completely sorted data when __spreadsort has an optimization to quit early in this case.

Situations where __spreadsort is slower than std::sort:

  • Data sorted in reverse order. Both std::sort and __spreadsort are faster on reverse-ordered data than randomized data, but std::sort speeds up more in this special case.

  • Very small amounts of data (< 1000 elements). For this reason there is a fallback in __spreadsort to std::sort if the input size is less than 1000, so performance is identical for small amounts of data in practice.

These functions are defined in namespace boost::sort::spreadsort.

2.2.2. Overloading

Tip
 In the Boost.Sort C++ Reference section, click on the appropriate overload, for example float_sort(RandomAccessIter, RandomAccessIter, Right_shift, Compare); to get full details of that overload.

Each of integer_sort, float_sort, and __string_sort have 3 main versions: The base version, which takes a first iterator and a last iterator, just like std::sort:

integer_sort(array.begin(), array.end());
float_sort(array.begin(), array.end());
string_sort(array.begin(), array.end());

The version with an overridden shift functor, providing flexibility in case the operator>> already does something other than a bitshift. The rightshift functor takes two args, first the data type, and second a natural number of bits to shift right.

For __string_sort this variant is slightly different; it needs a bracket functor equivalent to operator\[\], taking a number corresponding to the character offset, along with a second getlength functor to get the length of the string in characters. In all cases, this operator must return an integer type that compares with the operator< to provide the intended order (integers can be negated to reverse their order).

In other words (aside from negative floats, which are inverted as ints):

rightshift(A, n) < rightshift(B, n) -> A < B
A < B -> rightshift(A, 0) < rightshift(B, 0)

See [@../../example/rightshiftsample.cpp rightshiftsample.cpp] for a working example of integer sorting with a rightshift functor.

And a version with a comparison functor for maximum flexibility. This functor must provide the same sorting order as the integers returned by the rightshift (aside from negative floats):

rightshift(A, n) < rightshift(B, n) -> compare(A, B)
compare(A, B) -> rightshift(A, 0) < rightshift(B, 0)

Examples of functors are:

and these functors are used thus:

See [@../../example/stringfunctorsample.cpp stringfunctorsample.cpp] for a working example of sorting strings with all functors.

3. Bibliography

3.1. Steven Ross

Standard Template Library Sort Algorithms

C++ STL sort algorithms.

Radix Sort

A type of algorithm that sorts based upon distribution instead of by comparison. Wikipedia has an article about Radix Sorting. A more detailed description of various Radix Sorting algorithms is provided here:

Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168-179.

Introsort

A high-speed comparison-based sorting algorithm that takes ['[bigo](N * log(N))] time. See introsort and Musser, David R. (1997). "Introspective Sorting and Selection Algorithms", Software: Practice and Experience (Wiley) 27 (8), pp 983-993, available at Musser Introsort.

American Flag Sort

A high-speed hybrid string sorting algorithm that string_sort is partially based upon. See american_flag and Peter M. McIlroy, Keith Bostic, M. Douglas McIlroy. Engineering Radix Sort, Computing Systems 1993.

Adaptive Left Radix (ARL)

ARL (Adaptive Left Radix) is a hybrid cache-friendly integer sorting algorithm with comparable speed on random data to integer_sort, but does not have the optimizations for worst-case performance, causing it to perform poorly on certain types of unevenly distributed data.

Arne Maus, ARL, a faster in-place, cache friendly sorting algorithm, presented at NIK2002, Norwegian Informatics Conference, Kongsberg, 2002. Tapir, ISBN 82-91116-45-8.

Original Spreadsort

The algorithm that integer_sort was originally based on. integer_sort uses a smaller number of key bits at a time for better cache efficiency than the method described in the paper. The importance of cache efficiency grew as CPU clock speeds increased while main memory latency stagnated. See Steven J. Ross, The Spreadsort High-performance General-case Sorting Algorithm, Parallel and Distributed Processing Techniques and Applications, Volume 3, pp.1100-1106. Las Vegas Nevada. 2002. See [@../../doc/papers/original_spreadsort06_2002.pdf Steven Ross spreadsort_2002].

3.2. Francisco Tapia

  1. Introduction to Algorithms, 3rd Edition (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein)

  2. C++ STL Sort Algorithms

  3. Algorithm + Data Structures = Programs ( Nicklaus Wirth) Prentice Hall Series in Automatic Computation

  4. Structured Parallel Programming: Patterns for Efficient Computation (Michael McCool, James Reinders, Arch Robison)

3.3. Orson Peters

4. Gratitude

4.1. Steven Ross

To Steve’s wife Mary for her patience and support during the long process of converting spreadsort from a piece of C code to a template library.

To Phil Endecott and Frank Gennari for the improvements they’ve suggested and for testing. Without them this would have taken longer to develop or performed worse.

To Scott McMurray for the fast and safe float_mem_cast. That fix was critical for a high-performance cross-platform float_sort.

To Paul A. Bristow for refactoring the initial documentation to use Quickbooks.

To Steven Watanabe, Edouard Alligand, and others in the boost community for their helpful suggestions.

4.2. Francisco Tapia

To CESVIMA, Centro de Cálculo de la Universidad Politécnica de Madrid. When need machines for to tune this algorithm, I contacted with the investigation department of many Universities of Madrid. Only them, help me.

To Hartmut Kaiser, Adjunct Professor of Computer Science at Louisiana State University. By their faith in my work,

To Steven Ross, by their infinite patience in the long way in the develop of this algorithm, and their wise advises.

4.3. Orson Peters