algorithm used in this library is designed to provide best possible
worst-case performance, while still being cache-friendly. It provides
the better of 𝑶(N*log(K/S + S)) and 𝑶(N*log(N))
worst-case time, where K is the log of the range.
The log of the range is normally the length in bits of the data type;
32 for a 32-bit integer.
flash_sort (another hybrid algorithm), by comparison is
𝑶(N) for evenly distributed lists. The problem
flash_sort is merely an MSD radix
sort combined with 𝑶(N*N) insertion sort
to deal with small subsets where the MSD Radix Sort is inefficient,
so it is inefficient with chunks of data around the size at which it
insertion_sort, and ends up operating as an
enhanced MSD Radix Sort. For uneven distributions this makes it especially
instead, which provides 𝑶(N*log(N)) performance
for these medium-sized pieces. Also,
performance for even distributions comes at the cost of cache misses,
which on modern architectures are extremely expensive, and in testing
on modern systems ends up being slower than cutting up the data in
multiple, cache-friendly steps. Also worth noting is that on most modern
log2(available RAM)/log2(L1 cache size) is
around 3, where a cache miss takes more than 3 times as long as an
in-cache random-access, and the size of max_splits
is tuned to the size of the cache. On a computer where cache misses
aren't this expensive, max_splits could be increased
to a large value, or eliminated entirely, and
would have the same 𝑶(N) performance on even distributions.
Adaptive Left Radix (ALR) is similar to
more cache-friendly. It still uses insertion_sort. Because ALR uses
insertion_sort, it isn't efficient
to use the comparison-based fallback sort on large lists, and if the
data is clustered in small chunks just over the fallback size with
a few outliers, radix-based sorting iterates many times doing little
sorting with high overhead. Asymptotically, ALR is still 𝑶(N*log(K/S
+ S)), but with a very small S (about
2 in the worst case), which compares unfavorably with the 11 default
value of max_splits for Spreadsort.
ALR also does not have the 𝑶(N*log(N)) fallback,
so for small lists that are not evenly distributed it is extremely
inefficient. See the
testcases for examples; either replace the call to sort with a call
to ALR and update the ALR_THRESHOLD at the top, or as a quick comparison
get_max_count return ALR_THRESHOLD (20 by default
based upon the paper). These small tests take 4-10 times as long with
ALR as std::sort
in the author's testing, depending on the test system, because they
are trying to sort a highly uneven distribution. Normal Spreadsort
does much better with them, because
get_max_count is designed
around minimizing worst-case runtime.
burst_sort is an efficient hybrid algorithm for strings
that uses substantial additional memory.
are similar. A direct performance comparison would be welcome, but
an efficient version of
postal_sort was not found in a
search for source.
is most similar to the American
flag sort algorithm. The main difference is that it doesn't
bother trying to optimize how empty buckets/piles are handled, instead
just checking to see if all characters at the current index are equal.
Other differences are using std::sort
as the fallback algorithm, and a larger fallback size (256 vs. 16),
which makes empty pile handling less important.
Another difference is not applying the stack-size restriction. Because
of the equality check in
it would take m*m memory worth of strings to force
to create a stack of depth m. This problem isn't
a realistic one on modern systems with multi-megabyte stacksize limits,
where main memory would be exhausted holding the long strings necessary
to exceed the stacksize limit.
can be thought of as modernizing American
flag sort to take advantage of introsort
as a fallback algorithm. In the author's testing, American
flag sort (on
std::strings) had comparable runtime
but making a hybrid of the two allows reduced overhead and substantially