Static Sort
A very simple header only C++ class to create a static sort.
Uses templates to generate a Bose-Nelson sorting network on compile time.
To enable the magic to happen, please turn on optimizations. =)
(-O2 or -O3 depending on your compiler)
Installation
Just copy include/static_sort.h into your project and #include it. =)
You can also copy and paste the code from static_sort.h directly!
Requirements
A C++98 and above compiler.
Usage
// Fast for small randomly ordered arrays.
StaticSort<10> boseNelsonSort;
int a[10] = {6,7,3,2,4,0,9,1,8,5};
boseNelsonSort(a);
boseNelsonSort(a, std::less<int>()); // with less than comparator
// Fast for small arrays. Randomly ordered, reversed, in order.
StaticTimSort<10> timBoseNelsonSort;
int b[10] = {6,7,3,2,4,0,9,1,8,5};
timBoseNelsonSort(b);
timBoseNelsonSort(b, std::less<int>()); // with less than comparatorWorks on std::vectors, plain old arrays, or other array-like objects.
Accepts custom less than comparator.
Benchmarks
Here are the number of milliseconds taken to sort 1 million arrays of ints.
Compiled with clang -O3, a Macbook Air (Mid-2012) Intel i7-3667U 2GHz.
Random Order
6,7,3,2,4,0,9,1,8,5 -> 0,1,2,3,4,5,6,7,8,9
Reversed Order
9,8,7,6,5,4,3,2,1,0 -> 0,1,2,3,4,5,6,7,8,9
In Order
0,1,2,3,4,5,6,7,8,9 -> 0,1,2,3,4,5,6,7,8,9
For real-world data, it is recommended you use StaticTimSort.
Here are the average clocks per sort against other static sorts from
[http://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array]
(Lower is better)
These timings are for randomly ordered arrays.
Clang -O3 :
----------
Direct call to qsort library function : 326.81
Naive implementation (insertion sort) : 132.98
Insertion Sort (Daniel Stutzbach) : 104.04
Insertion Sort Unrolled : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum) : 81.55
Rank Order : 44.01
Rank Order with registers : 42.40
Sorting Networks (Daniel Stutzbach) : 88.06
Sorting Networks (Paul R) : 31.64
Sorting Networks 12 with Fast Swap : 29.68
Sorting Networks 12 reordered Swap : 28.61
Reordered Sorting Network w/ fast swap : 24.63
Templated Sorting Network (this class) : 25.37
Intel Compiler 16.0 -O3 :
------------------------
Direct call to qsort library function : 325.28
Naive implementation (insertion sort) : 97.38
Insertion Sort (Daniel Stutzbach) : 108.97
Insertion Sort Unrolled : 97.16
Insertion Sort Unrolled (Glenn Teitelbaum) : 109.65
Rank Order : 38.13
Rank Order with registers : 32.96
Sorting Networks (Daniel Stutzbach) : 85.56
Sorting Networks (Paul R) : 47.57
Sorting Networks 12 with Fast Swap : 41.13
Sorting Networks 12 reordered Swap : 37.42
Reordered Sorting Network w/ fast swap : 25.60
Templated Sorting Network (this class) : 29.09
Notes
On Sorting Pairs
If you want to sort pairs of 32-bit numbers (e.g. std::pair<int, int>),
it is recommended that you pack each pair of numbers into a single 64-bit number.
This will nudge the compiler to generate min/max instructions for fastest performance.
The overhead of packing and unpacking the pairs is negligible.
Sorting packed pairs is approximately 4-5x faster than sorting unpacked pairs.
At the time of writing, even the best modern compilers are unable to optimize this automatically.
For a simple example and benchmark, please look into bench_pair_sort.h.
It includes a little helper class for packing various types of 32-bit number pairs.
For Real World Data
Use StaticTimSort.
Like it?
Give it a star!
Let me know if you have used this library in any of your projects.
It helps me understand how it is used and plan new features.
Change Log
10 June 2020
- Added example for sorting pairs.
17 Oct 2019
-
Added argument to accept a less-than comparator.
-
Added a TimSort inspired Tim-Bose-Nelson sort to handle the case of already ordered arrays.
This adds only a very tiny overhead, and is only activated for arrays of 8 or more elements.
On average, it beats all the other sorts (except for the sorting-network) on
random, in-order and reversed-order arrays. :)
References
- http://stackoverflow.com/questions/2786899/fastest-sort-of-fixed-length-6-int-array
- https://github.com/atinm/bose-nelson/blob/master/bose-nelson.c
License
MIT