Home

Awesome

Intro

This document describes a stable adaptive hybrid bucket / quick / merge / drop sort named wolfsort. The bucket sort, forming the core of wolfsort, is not a comparison sort, so wolfsort can be considered a member of the radix-sort family. Quicksort and mergesort are well known. Dropsort gained popularity after it was reinvented as Stalin sort. A benchmark is available at the bottom.

Why a hybrid?

While an adaptive merge sort is very fast at sorting ordered data, its inability to effectively partition is its greatest weakness. A radix-like bucket sort, on the other hand, is unable to take advantage of sorted data. While quicksort is fast at partitioning, a bucket sort is faster on medium-sized arrays in the 1K - 1M element range. Dropsort in turn hybridizes surprisingly well with bucket and sample sorts.

History

Wolfsort 1, codename: quantumsort, started out with the concept that memory is in abundance on modern systems. I theorized that by allocating 8n memory performance could be increased by allowing a bucket sort to partition in one pass.

Not all the memory would be used or ever accessed however, which is why I envisioned it as a type of poor-man's quantum computing. The extra memory only serves to simplify computations. The concept kind of worked, except that large memory allocations in C can be either very fast or very slow. I didn't investigate why.

I also learned people don't like it when you use the term quantum computing outside of the proper context, or perhaps they were upset about wolfsort's voracious appetite for memory. Hence it was named.

Wolfsort 2, codename: flowsort, is when I reinvented counting sort. Instead of making 1 pass and using extra memory to deal with fluctuations in the data, flowsort makes one pass to calculate the bucket sizes, then makes a second pass to neatly fill the buckets.

Wolfsort 3, codename: dripsort, was inspired by the work of M. Lochbaum on rhsort to use a method similar to dropsort to deal with bucket overflow, and to calculate the minimum and maximum value to optimize for distributions with a small range of values. Dripsort once again makes one pass and uses around 4n memory to deal with fluctuations in the data. Compared to v1 this is a 50% reduction in memory allocation, while at the same time significantly increasing robustness.

Analyzer

Wolfsort uses the same analyzer as fluxsort to sort fully in-order and fully reverse-order distributions in n comparisons. The array is split into 4 segments for which a measure of presortedness is calculated. Mostly ordered segments are sorted with quadsort, while mostly random segments are sorted with wolfsort.

In addition, the minimum and maximum value in the distribution is obtained.

Setting the bucket size

For optimal performance wolfsort needs to have at least 8 buckets, end up with between 1 and 16 elements per bucket, so the bucket size is set to hold 8 elements on average. However, the buckets should remain in the L1 cache, so the maximum number of buckets is set at 65536.

This sets the optimal range for wolfsort between 8 * 8 (64) and 8 * 65536 (524,288) elements. Beyond the optimal range performance will degrade steadily. Once the average bucket size reaches the threshold of 18 elements (1,179,648 total elements) the sort becomes less optimal than quicksort, though it retains a computational advantage for a little while longer. However, by recursing once, wolfsort increases the optimal range to 1 trillion elements.

By computing the minimum and maximum value in the data distribution, the number of buckets are optimized further to target the sweet spot.

Dropsort

Dropsort was first proposed as an alternative sorting algorithm by David Morgan in 2006, it makes one pass and is lossy. The algorithm was reinvented in 2018 as Stalin sort. The concept of dropping hash entries in a non-lossy manner was independently developed by Marshall Lochbaum in 2018 and is utilized in his 2022 release of rhsort (Robin Hood Sort).

Wolfsort allocates 4n memory to allow some deviancy in the data distribution and minimize bucket overflow. In the case an element is too deviant and overflows the bucket, it is copied in-place to the input array. In near-optimal cases this results in a minimal drip, in the worst case it will result in a downpour of elements being copied to the input array.

While a centrally planned partitioning system has its weaknesses, the worst case is mostly alleviated by using fluxsort on the deviant elements once partitioning finishes. Fluxsort is adaptive and is generally strong against distributions where wolfsort is weak.

The overall performance gain from incorporating dropsort into wolfsort is approximately 20%, but can reach an order of magnitude when the fallback is synergetic with fluxsort. Deviant distributions can deceive wolfsort for a time, but not a very long time.

Small number sorting

Since wolfsort uses auxiliary memory, each partition is stable once partitioning completes. The next step is to sort the content of each bucket using fluxsort. If the number of elements in a bucket is below 32, fluxsort defaults to quadsort, which is highly optimized for sorting small arrays using a combination of branchless parity merges and twice-unguarded insertion.

Once each bucket is sorted, all that remains is merging the two distributions of compliant and deviant elements, and wolfsort is finished.

Memory overhead

Wolfsort requires 4n memory for the partitioning process and n / 4 memory (up to a maximum of 65536) for the buckets.

If not enough memory is available wolfsort falls back on fluxsort, which requires exactly 1n swap memory, and if that's not sufficient fluxsort falls back on quadsort which can sort in-place. It is an option to fall back on blitsort instead of quadsort, but since this would be an a-typical case, and increase dependencies, I didn't implement this.

64 bit integers

With the advent of fluxsort and crumsort the dominance of radix sorts has been pushed out of 64 bit territory. Increased memory-level-parallelism in future hardware, or algorithmic optimizations, might make radix sorts competitive again for 64 bit types. Wolfsort has a commented-out default to fluxsort.

128 bit floats

Wolfsort defaults to fluxsort for 128 bit floats. Keep in mind that in the real world you'll typically be sorting tables instead of arrays, so the benchmark isn't indicative of real world performance, as the sort will likely be copying 64 bit pointers instead of 128 bit floats.

God Mode

Wolfsort supports a cheat mode where the sort becomes unstable. This trick was taken from rhsort. Since wolfsort aspires to have some utility as a stable sort, this method is disabled by default, including in the benchmark.

In the benchmark rhsort does use this optimization, but it's only relevant for the random % 100 distribution. For 32 bit random integers rhsort easily beats wolfsort without an unfair advantage.

LLVM

When compiling with Clang, quadsort and fluxsort will take advantate of branchless ternary oprations, which gives a 15-30% performance gain. While not an algorithmic improvement, it's relevant to keep in mind, particularly when it comes to LLVM compiled Rust sorts with similar optimizations.

Interface

Wolfsort uses the same interface as qsort, which is described in man qsort.

Wolfsort also comes with the wolfsort_prim(void *array, size_t nmemb, size_t size) function to perform primitive comparisons on arrays of 32 and 64 bit integers. Nmemb is the number of elements, while size should be either sizeof(int) or sizeof(long long) for signed integers, and sizeof(int) + 1 or sizeof(long long) + 1 for unsigned integers. Support for the char and short types can be easily added in wolfsort.h.

Wolfsort can only sort arrays of primitive integers by default. Wolfsort should be able to sort tables with some minor changes, but it'll require a different interface than qsort() provides.

Proof of concept

Wolfsort is primarily a proof of concept for a hybrid bucket / comparison sort. It only supports non-negative integers.

I'll briefly mention other sorting algorithms listed in the benchmark code / graphs. They can all be considered the fastest algorithms currently available in their particular class.

Blitsort

Blitsort is a hybrid in-place stable adaptive rotate quick / merge sort.

Crumsort

Crumsort is a hybrid in-place unstable adaptive quick / rotate merge sort.

Quadsort

Quadsort is an adaptive mergesort. It supports rotations as a fall-back to sort in-place. It has very good performance when it comes to sorting tables and generally outperforms timsort.

Gridsort

Gridsort is a stable comparison sort which stores data in a 2 dimensional self-balancing grid. It has some interesting properties and was the fastest comparison sort for random data for a brief period of time.

Fluxsort

Fluxsort is a hybrid stable branchless out-of-place quick / merge sort.

Piposort

Piposort is a simplified branchless quadsort with a much smaller code size and complexity while still being very fast. Piposort might be of use to people who want to port quadsort. This is a lot easier when you start out small.

rhsort

rhsort is a hybrid stable out-of-place counting / radix / drop / insertion sort. It has exceptional performance on random and generic data for medium array sizes.

Ska sort

Ska sort is an advanced radix sort that can sort strings and floats as well. It offers both an in-place and out-of-place version, but since the out-of-place unstable version is not very competitive with wolfsort, I only benchmark the stable and faster ska_sort_copy variant.

Big O

                 ┌───────────────────────┐┌────────────────────┐
                 │comparisons            ││swap memory         │
┌───────────────┐├───────┬───────┬───────┤├──────┬──────┬──────┤┌──────┐┌─────────┐┌─────────┐┌─────────┐
│name           ││min    │avg    │max    ││min   │avg   │max   ││stable││partition││adaptive ││compares │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│blitsort       ││n      │n log n│n log n││1     │1     │1     ││yes   ││yes      ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│crumsort       ││n      │n log n│n log n││1     │1     │1     ││no    ││yes      ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│fluxsort       ││n      │n log n│n log n││n     │n     │n     ││yes   ││yes      ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│gridsort       ││n      │n log n│n log n││n     │n     │n     ││yes   ││yes      ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│quadsort       ││n      │n log n│n log n││1     │n     │n     ││yes   ││no       ││yes      ││yes      │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│wolfsort       ││n      │n log n│n log n││n     │n     │n     ││yes   ││yes      ││yes      ││hybrid   │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│rhsort         ││n      │n log n│n log n││n     │n     │n     ││yes   ││yes      ││semi     ││hybrid   │
├───────────────┤├───────┼───────┼───────┤├──────┼──────┼──────┤├──────┤├─────────┤├─────────┤├─────────┤
│skasort_copy   ││n k    │n k    │n k    ││n     │n     │n     ││yes   ││yes      ││no       ││no       │
└───────────────┘└───────┴───────┴───────┘└──────┴──────┴──────┘└──────┘└─────────┘└─────────┘└─────────┘

Benchmark for Wolfsort v1.2.1.3

rhsort vs wolfsort vs ska_sort_copy on 100K elements

The following benchmark was on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1) on 100,000 32 bit integers. The source code was compiled using g++ -O3 -fpermissive bench.c. All comparisons are inlined through the cmp macro. A table with the best and average time in seconds can be uncollapsed below the bar graph.

Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageLoopsSamplesDistribution
wolfsort100000640.0030060.0030630100random order
skasort100000640.0018180.0018420100random order
NameItemsTypeBestAverageLoopsSamplesDistribution
rhsort100000320.0007060.0007290100random order
wolfsort100000320.0010000.0010260100random order
skasort100000320.0006260.0006400100random order
rhsort100000320.0001150.0001180100random % 100
wolfsort100000320.0003760.0003820100random % 100
skasort100000320.0007800.0007930100random % 100
rhsort100000320.0003020.0003170100ascending order
wolfsort100000320.0000860.0000880100ascending order
skasort100000320.0007090.0007200100ascending order
rhsort100000320.0006150.0006330100ascending saw
wolfsort100000320.0003790.0004070100ascending saw
skasort100000320.0006240.0006370100ascending saw
rhsort100000320.0005910.0006150100pipe organ
wolfsort100000320.0002480.0002580100pipe organ
skasort100000320.0006240.0006390100pipe organ
rhsort100000320.0004000.0004200100descending order
wolfsort100000320.0000970.0001010100descending order
skasort100000320.0006840.0006930100descending order
rhsort100000320.0006120.0006290100descending saw
wolfsort100000320.0003890.0003930100descending saw
skasort100000320.0006270.0006390100descending saw
rhsort100000320.0006330.0006640100random tail
wolfsort100000320.0004670.0004730100random tail
skasort100000320.0006220.0006360100random tail
rhsort100000320.0006710.0006850100random half
wolfsort100000320.0006890.0007060100random half
skasort100000320.0006280.0006410100random half
rhsort100000320.0020190.0020520100ascending tiles
wolfsort100000320.0006830.0006910100ascending tiles
skasort100000320.0010960.0011130100ascending tiles
rhsort100000320.0008370.0008710100bit reversal
wolfsort100000320.0008870.0009280100bit reversal
skasort100000320.0007750.0007820100bit reversal
rhsort100000320.0001180.0001230100random % 4
wolfsort100000320.0003680.0003710100random % 4
skasort100000320.0007850.0008090100random % 4
rhsort100000320.0012780.0014650100semi random
wolfsort100000320.0007920.0008110100semi random
skasort100000320.0008050.0008210100semi random
rhsort100000320.0001980.0002020100random signal
wolfsort100000320.0008150.0008290100random signal
skasort100000320.0010990.0011180100random signal
</details>

The following benchmark was on WSL 2 gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04). The source code was compiled using g++ -O3 -w -fpermissive bench.c. It measures the performance on random data with array sizes ranging from 10 to 10,000,000. It's generated by running the benchmark using 10000000 0 0 as the argument. The benchmark is weighted, meaning the number of repetitions halves each time the number of items doubles. A table with the best and average time in seconds can be uncollapsed below the bar graph.

Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageComparesSamplesDistribution
rhsort10320.1350950.1370110.010random 10
wolfsort10320.0520870.0529860.010random 10
skasort10320.0998530.1001980.010random 10
rhsort100320.0692520.0704210.010random 100
wolfsort100320.1322080.1328240.010random 100
skasort100320.2320070.2325070.010random 100
rhsort1000320.0559160.0561300.010random 1000
wolfsort1000320.1016110.1019130.010random 1000
skasort1000320.0547570.0550500.010random 1000
rhsort10000320.0570620.0573590.010random 10000
wolfsort10000320.1185980.1193730.010random 10000
skasort10000320.0597860.0601890.010random 10000
rhsort100000320.0712730.0733100.010random 100000
wolfsort100000320.1026390.1039170.010random 100000
skasort100000320.0641200.0646150.010random 100000
rhsort1000000320.1810590.1875630.010random 1000000
wolfsort1000000320.1466300.1475980.010random 1000000
skasort1000000320.0702500.0715710.010random 1000000
rhsort10000000320.4121070.425066010random 10000000
wolfsort10000000320.1931200.200947010random 10000000
skasort10000000320.1157210.116621010random 10000000
</details>

Benchmark for Wolfsort v1.2.1.3

fluxsort vs gridsort vs quadsort vs wolfsort on 100K elements

The following benchmark was on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). The source code was compiled using g++ -O3 -fpermissive bench.c. All comparisons are inlined through the cmp macro. A table with the best and average time in seconds can be uncollapsed below the bar graph.

Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageComparesSamplesDistribution
fluxsort1000001280.0083280.0084240100random order
gridsort1000001280.0078230.0079320100random order
quadsort1000001280.0082600.0083530100random order
wolfsort1000001280.0083300.0084150100random order
NameItemsTypeBestAverageComparesSamplesDistribution
fluxsort100000640.0019710.0019910100random order
gridsort100000640.0023700.0023980100random order
quadsort100000640.0022300.0022540100random order
wolfsort100000640.0030230.0030680100random order
NameItemsTypeBestAverageLoopsSamplesDistribution
fluxsort100000320.0018680.0019010100random order
gridsort100000320.0023240.0023570100random order
quadsort100000320.0021490.0021740100random order
wolfsort100000320.0009880.0010190100random order
fluxsort100000320.0007330.0007400100random % 100
gridsort100000320.0019210.0019410100random % 100
quadsort100000320.0016270.0016450100random % 100
wolfsort100000320.0003740.0003780100random % 100
fluxsort100000320.0000430.0000440100ascending order
gridsort100000320.0002640.0002710100ascending order
quadsort100000320.0000520.0000530100ascending order
wolfsort100000320.0000870.0000890100ascending order
fluxsort100000320.0003050.0003140100ascending saw
gridsort100000320.0006210.0006410100ascending saw
quadsort100000320.0004110.0004170100ascending saw
wolfsort100000320.0003790.0003840100ascending saw
fluxsort100000320.0001930.0002030100pipe organ
gridsort100000320.0004460.0004860100pipe organ
quadsort100000320.0002520.0002600100pipe organ
wolfsort100000320.0002480.0002590100pipe organ
fluxsort100000320.0000540.0000550100descending order
gridsort100000320.0002840.0002950100descending order
quadsort100000320.0000680.0000700100descending order
wolfsort100000320.0000970.0001000100descending order
fluxsort100000320.0003150.0003250100descending saw
gridsort100000320.0006520.0006670100descending saw
quadsort100000320.0004400.0004460100descending saw
wolfsort100000320.0003890.0003930100descending saw
fluxsort100000320.0006070.0006190100random tail
gridsort100000320.0008470.0008600100random tail
quadsort100000320.0006850.0006940100random tail
wolfsort100000320.0004640.0004710100random tail
fluxsort100000320.0010740.0010810100random half
gridsort100000320.0013320.0013550100random half
quadsort100000320.0012300.0012430100random half
wolfsort100000320.0006860.0006960100random half
fluxsort100000320.0003170.0003240100ascending tiles
gridsort100000320.0006650.0006930100ascending tiles
quadsort100000320.0007890.0008020100ascending tiles
wolfsort100000320.0006860.0006930100ascending tiles
fluxsort100000320.0017140.0017510100bit reversal
gridsort100000320.0020450.0020600100bit reversal
quadsort100000320.0020830.0021000100bit reversal
wolfsort100000320.0008880.0009120100bit reversal
fluxsort100000320.0002150.0002230100random % 4
gridsort100000320.0012830.0013050100random % 4
quadsort100000320.0010800.0010900100random % 4
wolfsort100000320.0003690.0003710100random % 4
fluxsort100000320.0010720.0010980100semi random
gridsort100000320.0013550.0013770100semi random
quadsort100000320.0010620.0010740100semi random
wolfsort100000320.0007890.0008030100semi random
fluxsort100000320.0010790.0010990100random signal
gridsort100000320.0012960.0013060100random signal
quadsort100000320.0010140.0010270100random signal
wolfsort100000320.0008160.0008280100random signal
</details>

fluxsort vs gridsort vs quadsort vs wolfsort on 10M elements

Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageComparesSamplesDistribution
fluxsort100000001281.2423951.264809010random order
gridsort100000001281.0487481.110490010random order
quadsort100000001281.4076391.418088010random order
wolfsort100000001281.2390991.241608010random order
NameItemsTypeBestAverageComparesSamplesDistribution
fluxsort10000000640.3173270.318203010random order
gridsort10000000640.3324300.334392010random order
quadsort10000000640.4382570.439139010random order
wolfsort10000000640.4819770.484055010random order
NameItemsTypeBestAverageLoopsSamplesDistribution
fluxsort10000000320.2693510.271460010random order
gridsort10000000320.3220990.323899010random order
quadsort10000000320.3644570.365617010random order
wolfsort10000000320.1897800.190911010random order
fluxsort10000000320.0899730.090849010random % 100
gridsort10000000320.1722220.173147010random % 100
quadsort10000000320.2483610.250615010random % 100
wolfsort10000000320.0864730.087067010random % 100
fluxsort10000000320.0064370.006574010ascending order
gridsort10000000320.0323210.032798010ascending order
quadsort10000000320.0117360.012125010ascending order
wolfsort10000000320.0108880.011015010ascending order
fluxsort10000000320.0749400.075525010ascending saw
gridsort10000000320.0674780.067893010ascending saw
quadsort10000000320.0971330.098004010ascending saw
wolfsort10000000320.0817970.082794010ascending saw
fluxsort10000000320.0645770.065593010pipe organ
gridsort10000000320.0489320.049336010pipe organ
quadsort10000000320.0825330.083781010pipe organ
wolfsort10000000320.0703340.071158010pipe organ
fluxsort10000000320.0098070.010104010descending order
gridsort10000000320.0345830.034814010descending order
quadsort10000000320.0113960.011639010descending order
wolfsort10000000320.0141980.014544010descending order
fluxsort10000000320.0782790.079071010descending saw
gridsort10000000320.0697020.070109010descending saw
quadsort10000000320.1018260.102801010descending saw
wolfsort10000000320.0851010.085973010descending saw
fluxsort10000000320.1219480.122561010random tail
gridsort10000000320.1093410.110117010random tail
quadsort10000000320.1533240.153797010random tail
wolfsort10000000320.1035580.104152010random tail
fluxsort10000000320.1813470.183186010random half
gridsort10000000320.1856910.186592010random half
quadsort10000000320.2252650.225897010random half
wolfsort10000000320.1598190.160569010random half
fluxsort10000000320.0736730.074755010ascending tiles
gridsort10000000320.1263090.126626010ascending tiles
quadsort10000000320.1653320.167541010ascending tiles
wolfsort10000000320.0934240.094040010ascending tiles
fluxsort10000000320.2716790.272589010bit reversal
gridsort10000000320.2965630.297984010bit reversal
quadsort10000000320.3691050.370652010bit reversal
wolfsort10000000320.2512090.252891010bit reversal
fluxsort10000000320.0560110.056552010random % 4
gridsort10000000320.1911790.194017010random % 4
quadsort10000000320.1924660.193967010random % 4
wolfsort10000000320.0816680.082543010random % 4
fluxsort10000000320.0542310.054571010semi random
gridsort10000000320.1465340.146907010semi random
quadsort10000000320.1974620.200010010semi random
wolfsort10000000320.1926030.194365010semi random
fluxsort10000000320.1730800.176575010random signal
gridsort10000000320.1375900.137932010random signal
quadsort10000000320.1809390.181778010random signal
wolfsort10000000320.1611810.161714010random signal
</details>

blitsort vs crumsort vs pdqsort vs wolfsort on 100K elements

The following benchmark was on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1). The source code was compiled using g++ -O3 -fpermissive bench.c. All comparisons are inlined through the cmp macro. A table with the best and average time in seconds can be uncollapsed below the bar graph.

Blitsort uses 512 elements of auxiliary memory, crumsort 512, pdqsort 64, and wolfsort 100000. Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageComparesSamplesDistribution
blitsort1000001280.0108640.0109940100random order
crumsort1000001280.0081430.0082220100random order
pdqsort1000001280.0059540.0060630100random order
wolfsort1000001280.0083080.0083960100random order
NameItemsTypeBestAverageComparesSamplesDistribution
blitsort100000640.0023260.0023540100random order
crumsort100000640.0018350.0018480100random order
pdqsort100000640.0027520.0028060100random order
wolfsort100000640.0030140.0030690100random order
NameItemsTypeBestAverageLoopsSamplesDistribution
blitsort100000320.0020940.0021170100random order
crumsort100000320.0017640.0017790100random order
pdqsort100000320.0027470.0027700100random order
wolfsort100000320.0009830.0010160100random order
blitsort100000320.0008800.0008910100random % 100
crumsort100000320.0006020.0006410100random % 100
pdqsort100000320.0007950.0008050100random % 100
wolfsort100000320.0003760.0003810100random % 100
blitsort100000320.0000430.0000450100ascending order
crumsort100000320.0000430.0000440100ascending order
pdqsort100000320.0000840.0000880100ascending order
wolfsort100000320.0000860.0000880100ascending order
blitsort100000320.0004400.0004500100ascending saw
crumsort100000320.0004100.0004190100ascending saw
pdqsort100000320.0032220.0032460100ascending saw
wolfsort100000320.0003790.0003820100ascending saw
blitsort100000320.0002420.0002510100pipe organ
crumsort100000320.0002290.0002430100pipe organ
pdqsort100000320.0028420.0028640100pipe organ
wolfsort100000320.0002490.0002570100pipe organ
blitsort100000320.0000540.0000550100descending order
crumsort100000320.0000540.0000550100descending order
pdqsort100000320.0001900.0001980100descending order
wolfsort100000320.0000970.0001000100descending order
blitsort100000320.0004520.0004660100descending saw
crumsort100000320.0004210.0004310100descending saw
pdqsort100000320.0042000.0042450100descending saw
wolfsort100000320.0003830.0004020100descending saw
blitsort100000320.0007820.0008290100random tail
crumsort100000320.0007140.0007550100random tail
pdqsort100000320.0026380.0027590100random tail
wolfsort100000320.0004630.0004830100random tail
blitsort100000320.0012100.0012750100random half
crumsort100000320.0010630.0010960100random half
pdqsort100000320.0027380.0027800100random half
wolfsort100000320.0006850.0007120100random half
blitsort100000320.0011050.0012780100ascending tiles
crumsort100000320.0013930.0014350100ascending tiles
pdqsort100000320.0023670.0023980100ascending tiles
wolfsort100000320.0006820.0006890100ascending tiles
blitsort100000320.0019560.0019880100bit reversal
crumsort100000320.0017620.0017940100bit reversal
pdqsort100000320.0027310.0027580100bit reversal
wolfsort100000320.0008900.0009210100bit reversal
blitsort100000320.0003280.0003410100random % 4
crumsort100000320.0002060.0002160100random % 4
pdqsort100000320.0003820.0003910100random % 4
wolfsort100000320.0003670.0003780100random % 4
blitsort100000320.0012090.0012440100semi random
crumsort100000320.0003090.0003190100semi random
pdqsort100000320.0004790.0005000100semi random
wolfsort100000320.0007910.0008280100semi random
blitsort100000320.0018930.0019260100random signal
crumsort100000320.0017140.0017420100random signal
pdqsort100000320.0029500.0029760100random signal
wolfsort100000320.0008140.0008340100random signal
</details>

blitsort vs crumsort vs pdqsort vs wolfsort on 10M elements

Blitsort uses 512 elements of auxiliary memory, crumsort 512, pdqsort 64, and wolfsort 100000000.

Graph

<details><summary><b>data table</b></summary>
NameItemsTypeBestAverageComparesSamplesDistribution
blitsort100000001282.1726222.191956010random order
crumsort100000001281.1343281.135821010random order
pdqsort100000001280.8056200.808041010random order
wolfsort100000001281.2371741.238863010random order
NameItemsTypeBestAverageComparesSamplesDistribution
blitsort10000000640.4343560.443134010random order
crumsort10000000640.2500650.251453010random order
pdqsort10000000640.3595860.360388010random order
wolfsort10000000640.4809040.482835010random order
NameItemsTypeBestAverageLoopsSamplesDistribution
blitsort10000000320.3320710.339524010random order
crumsort10000000320.2315840.232056010random order
pdqsort10000000320.3477930.348437010random order
wolfsort10000000320.1892500.189762010random order
blitsort10000000320.1267920.128439010random % 100
crumsort10000000320.0606830.061353010random % 100
pdqsort10000000320.0792840.079891010random % 100
wolfsort10000000320.0865770.087157010random % 100
blitsort10000000320.0065810.006784010ascending order
crumsort10000000320.0066900.006801010ascending order
pdqsort10000000320.0117120.011851010ascending order
wolfsort10000000320.0109580.011520010ascending order
blitsort10000000320.0705140.071260010ascending saw
crumsort10000000320.0648290.066035010ascending saw
pdqsort10000000320.5609950.561774010ascending saw
wolfsort10000000320.0816440.082279010ascending saw
blitsort10000000320.0412200.041924010pipe organ
crumsort10000000320.0393350.040018010pipe organ
pdqsort10000000320.3636330.364187010pipe organ
wolfsort10000000320.0705360.071400010pipe organ
blitsort10000000320.0102710.010549010descending order
crumsort10000000320.0102540.010499010descending order
pdqsort10000000320.0231290.023708010descending order
wolfsort10000000320.0145830.015316010descending order
blitsort10000000320.0734100.074402010descending saw
crumsort10000000320.0682840.069154010descending saw
pdqsort10000000320.9421420.958606010descending saw
wolfsort10000000320.0853380.086014010descending saw
blitsort10000000320.1240890.130327010random tail
crumsort10000000320.1030300.104337010random tail
pdqsort10000000320.3378620.342594010random tail
wolfsort10000000320.1033810.108048010random tail
blitsort10000000320.1914790.193036010random half
crumsort10000000320.1467320.147742010random half
pdqsort10000000320.3428030.343424010random half
wolfsort10000000320.1595150.160787010random half
blitsort10000000320.1822560.190378010ascending tiles
crumsort10000000320.1888750.195063010ascending tiles
pdqsort10000000320.2857770.286996010ascending tiles
wolfsort10000000320.0937090.094315010ascending tiles
blitsort10000000320.3249830.326345010bit reversal
crumsort10000000320.2308720.231599010bit reversal
pdqsort10000000320.3439150.344677010bit reversal
wolfsort10000000320.2503310.251319010bit reversal
blitsort10000000320.0611970.062058010random % 4
crumsort10000000320.0301340.030564010random % 4
pdqsort10000000320.0434920.043673010random % 4
wolfsort10000000320.0815480.082020010random % 4
blitsort10000000320.0666860.067764010semi random
crumsort10000000320.0454790.046088010semi random
pdqsort10000000320.0602530.060612010semi random
wolfsort10000000320.1905050.191946010semi random
blitsort10000000320.2724560.274928010random signal
crumsort10000000320.2241150.225966010random signal
pdqsort10000000320.3827420.384505010random signal
wolfsort10000000320.1609460.161769010random signal
</details>