• Stars
    star
    50
  • Rank 577,233 (Top 12 %)
  • Language
    C++
  • Created almost 10 years ago
  • Updated 4 months ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Boost.Sort

BOOST SORT

Introduction

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

This library provides stable and not stable sorting algorithms, in single thread and parallel versions.

These algorithms do not use any other library or utility. The parallel algorithms need a C++11 compliant compiler.

Detailed boost API documentation also available.

Single Thread Algorithms

Algorithm Stable Additional memory Best, average, and worst case Comparison method
spreadsort no key_length N, N sqrt(LogN), Hybrid radix sort
min(N logN, N key_length)
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 a novel hybrid radix sort algorithm, extremely fast, designed and developed by Steven Ross. (paper)

  • pdqsort is a improvement of the quick sort algorithm, designed and developed by Orson Peters. (paper)

  • spinsort is a stable sort, fast with random and with near sorted data, designed and developed by Francisco Tapia.

  • flat_stable_sort stable sort with a small additional memory (around 1% of the size of the data), provide the 80% - 90% of the speed of spinsort, being fast with random and with near sorted data, designed and developed by Francisco Tapia. (paper)

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 parallel sort algorithm, very fast, with low additional memory consumption, conceived and implemented by Francisco Tapia. (paper)

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

Installation

  • This library is include only.
  • Don't need to link with any static or dynamic library. Only need a C++11 compiler
  • Only need to include the file boost/sort/sort.hpp

Author and Copyright

This library is integrated in the Boost Library.

Copyright 2017

Distributed under the Boost Software License, Version 1.0.

More Repositories

1

boost

Super-project for modularized Boost
HTML
6,236
star
2

beast

HTTP and WebSocket built on Boost.Asio in C++11
C++
4,355
star
3

hana

Your standard library for metaprogramming
C++
1,690
star
4

compute

A C++ GPU Computing Library for OpenCL
C++
1,487
star
5

pfr

std::tuple like methods for user defined types without any macro or boilerplate code
C++
1,221
star
6

asio

Boost.org asio module
C++
1,212
star
7

hof

Higher-order functions for c++
C++
504
star
8

geometry

Boost.Geometry - Generic Geometry Library | Requires C++14 since Boost 1.75
C++
457
star
9

fiber

userland threads
C++
457
star
10

json

A C++11 library for parsing and serializing JSON to and from a DOM container in memory.
C++
434
star
11

python

Boost.org python module
C++
432
star
12

spirit

Boost.org spirit module
C++
390
star
13

stacktrace

C++ library for storing and printing backtraces.
C++
374
star
14

histogram

Fast multi-dimensional generalized histogram with convenient interface for C++14
C++
315
star
15

math

Boost.org math module
C++
310
star
16

context

Assembly
299
star
17

graph

Boost.org graph module
C++
285
star
18

leaf

Lightweight Error Augmentation Framework
C++
275
star
19

mysql

MySQL C++ client based on Boost.Asio
C++
254
star
20

mp11

C++11 metaprogramming library
C++
239
star
21

build

B2 makes it easy to build C++ projects, everywhere.
C++
224
star
22

redis

An async redis client designed for performance and scalability
C++
223
star
23

cobalt

Coroutines for C++20 & asio
C++
222
star
24

safe_numerics

Replacements to standard numeric types which throw exceptions on errors
C++
208
star
25

thread

Boost.org thread module
C++
198
star
26

multiprecision

Boost.Multiprecision
C++
195
star
27

url

Boost.URL is a library for manipulating Uniform Resource Identifiers (URIs) and Locators (URLs).
C++
186
star
28

test

The reference C++ unit testing framework (TDD, xUnit, C++03/11/14/17)
C++
178
star
29

gil

Boost.GIL - Generic Image Library | Requires C++14 since Boost 1.80
C++
178
star
30

log

Boost Logging library
C++
173
star
31

nowide

Boost.Nowide - Standard library functions with UTF-8 API on Windows
C++
171
star
32

filesystem

Boost.org filesystem module
C++
158
star
33

core

Boost Core Utilities
C++
133
star
34

interprocess

Boost.org interprocess module
C++
132
star
35

callable_traits

modern C++ type traits and metafunctions for callable types
C++
129
star
36

coroutine2

Boost.Coroutine2
C++
127
star
37

lockfree

Boost.Lockfree
C++
120
star
38

serialization

Boost.org serialization module
C++
119
star
39

process

Boost Process
C++
117
star
40

wiki

Boost Wiki
115
star
41

algorithm

Boost.org algorithm module
C++
112
star
42

ublas

Boost.uBlas
C++
108
star
43

smart_ptr

Boost.org smart_ptr module
C++
108
star
44

yap

A C++14-and-later expression template library
C++
107
star
45

container

STL-like containers from Boost
C++
101
star
46

program_options

Boost.org program_options module
C++
92
star
47

preprocessor

Boost.org preprocessor module
C++
91
star
48

cmake

CMake support infrastructure Boost submodule
CMake
87
star
49

uuid

Boost.org uuid module
C++
84
star
50

regex

Boost.org regex module
C++
84
star
51

qvm

Boost Quaternions, Vectors, Matrices library
C++
80
star
52

coroutine

Boost.Coroutine
C++
79
star
53

signals2

Boost.org signals2 module
C++
74
star
54

config

Boost.org config module
C++
72
star
55

stl_interfaces

A C++14 and later CRTP template for defining iterators
C++
69
star
56

describe

A C++14 reflection library
C++
67
star
57

variant2

A never-valueless, strong guarantee implementation of std::variant
C++
66
star
58

date_time

Boost.org date_time module
C++
65
star
59

poly_collection

Fast containers of polymorphic objects.
C++
63
star
60

unordered

Boost.org unordered module
C++
62
star
61

static_string

A fixed capacity dynamically sized string
C++
62
star
62

type_traits

Boost.org type_traits module
C++
61
star
63

winapi

Windows API declarations without <windows.h>, for internal Boost use.
C++
58
star
64

atomic

Boost.Atomic
C++
57
star
65

mpi

Boost.org mpi module
C++
56
star
66

property_tree

Boost.org property_tree module
C++
56
star
67

intrusive

Boost.org intrusive module
C++
54
star
68

circular_buffer

Boost.org circular_buffer module
C++
53
star
69

optional

Boost.org optional module
C++
50
star
70

polygon

Boost.org polygon module
C++
48
star
71

fusion

Boost.org fusion module
C++
47
star
72

utility

Boost.org utility module
C++
47
star
73

variant

Boost.org variant module
C++
45
star
74

endian

Boost Endian library
C++
45
star
75

odeint

Boost.odeint
C++
44
star
76

range

Boost.org range module
C++
43
star
77

mpl

Boost.org mpl module
C++
43
star
78

predef

Boost.Predef (a Boost C++ Library)
C
43
star
79

iostreams

Boost.org iostreams module
C++
43
star
80

metaparse

A library for generating compile time parsers parsing embedded DSL code as part of the C++ compilation process
C++
42
star
81

multi_index

Boost.org multi_index module
C++
41
star
82

outcome

Provides very lightweight outcome<T> and result<T> (Boost edition)
C++
40
star
83

contract

Contract programming for C++
C++
39
star
84

pool

Boost.org pool module
C++
37
star
85

dynamic_bitset

Boost.org dynamic_bitset module
C++
36
star
86

system

Boost.org system module
C++
35
star
87

random

Boost.org random module
C++
34
star
88

assert

Boost.Assert
C++
32
star
89

container_hash

Generic hash function for STL style unordered containers
C++
32
star
90

any

Boost.org any module
C++
32
star
91

locale

Boost.Locale
C++
31
star
92

msm

Boost.org msm module
C++
30
star
93

phoenix

Boost.org phoenix module
C++
28
star
94

units

Boost.org units module
C++
28
star
95

bind

Boost.org bind module
C++
26
star
96

charconv

C++11 compatible charconv
C++
26
star
97

format

Boost.org format module
C++
25
star
98

multi_array

Boost.org multi_array module
C++
25
star
99

lexical_cast

General literal text conversions, such as an int represented as a string, or vice versa
C++
25
star
100

website

The boost website.
HTML
24
star