Hackage :: [Package]

vector-quicksort: Fast and flexible quicksort implementation for mutable vectors

[ algorithms, apache, library ] [ Propose Tags ] [ Report a vulnerability ]

Quicksort implementation developed with performance in mind. Has good default single-threaded sort and provides parallelised versions that are actually faster than the single-threaded version. Users can define new parallelisation methods.

Good starting point:

import Data.Vector.Algorithms.Quicksort qualified as Quick

Then call as

Quick.sort xs
[Skip to Readme]

library vector-quicksort

Modules

[Index] [Quick Jump]

library vector-quicksort:test-foreign-sort

library vector-quicksort:test-predefined-sorts

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1, 0.2
Change log Changelog.md
Dependencies base (>=4.15 && <5), primitive, stm, system-cxx-std-lib (==1.0), vector (>=0.13), vector-quicksort [details]
License Apache-2.0
Copyright (c) Sergey Vinokurov 2022
Author Sergey Vinokurov
Maintainer Sergey Vinokurov <serg.foo@gmail.com>
Category Algorithms
Home page https://github.com/sergv/vector-quicksort
Source repo head: git clone https://github.com/sergv/vector-quicksort.git
Uploaded by SergeyVinokurov at 2024-12-17T23:08:58Z
Distributions NixOS:0.1, Stackage:0.2
Downloads 101 total (19 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2024-12-17 [all 1 reports]

Readme for vector-quicksort-0.2

[back to package description]

build

Synopsis

This package features reasonable sort function that is a good default for sorting mutable vectors using well-known quicksort algorithm. During development one of the goals was making it perform on par with C++’s std::sort, i.e. fast.

While providing reasonably good single-threaded default sorting, the algorithm in this package is also parallelisable and can provide ways to run on multiple cores using either threads or sparks, so bigger vectors can be sorted even faster.

Algorithm details

Technically it’s an introsort, i.e. pathological O(N^2) quicksort case will get delegated to heapsort when recursion gets too deep, thus making algorithm reliably O(N * log(N)).

Benchmarks

The benchmark is to generate some random arrays of different length and sort them. For each array size N two versions are generated: one from range [0, N] (with few duplicates below), another from [0, N / 1000] (with many duplicates below) to introduce duplicates. And there’s one reasonably big array (around 40,000 elements) with lots of duplicates that I managed to come by in the real world under Sorting fuzzy matching scores vector that comes from test.txt file in this repository. with

Test setup: AMD Ryzen 9 7950X3D 16-Core Processor, Intel i5-9600K CPU @ 3.70GHz, GHC 9.10.1.

The default sort exported in Data.Vector.Algorithms.Quicksort is Sequential and Median3or5.

NB vector-algorithms benchmark is not included below (but it’s still there and will run for you locally) because it doesn’t specialise by default and in that case takes around 100 times more time than C++. That’s not representative, when this library doesn’t specialise it suffers similar slowdown (please refer to the docs on how to alleviate that).

$ cabal run bench -- -j1 --time-mode wall --timeout 300 -p '!/vector-algorithms heapsort/'
All
  Sorting fuzzy matching scores vector
    C++:                              OK
      228  μs ±  22 μs
    Sequential ST Median3:            OK
      104  μs ± 6.1 μs, 0.45x
    Sequential IO Median3:            OK
      104  μs ± 6.0 μs, 0.46x
    ParStrategies ST Median3:         OK
      102  μs ± 5.6 μs, 0.45x
    ParStrategies IO Median3:         OK
      104  μs ± 5.6 μs, 0.46x
    Sequential ST Median3or5:         OK
      94.6 μs ± 5.7 μs, 0.41x
    Sequential IO Median3or5:         OK
      96.7 μs ± 5.5 μs, 0.42x
    ParStrategies ST Median3or5:      OK
      95.0 μs ± 5.6 μs, 0.42x
    ParStrategies IO Median3or5:      OK
      95.9 μs ± 5.9 μs, 0.42x
    Threads IO Median3:               OK
      104  μs ± 8.2 μs, 0.45x
    Threads IO Median3or5:            OK
      98.0 μs ± 5.5 μs, 0.43x
    fallback heapsort:                OK
      1.53 ms ±  97 μs, 6.70x
  Int64
    Sorting 10 random arrays of length 16 with few duplicates
      C++:                            OK
        673  ns ±  65 ns
      Sequential ST Median3:          OK
        442  ns ±  21 ns, 0.66x
      Sequential IO Median3:          OK
        432  ns ±  37 ns, 0.64x
      ParStrategies ST Median3:       OK
        437  ns ±  38 ns, 0.65x
      ParStrategies IO Median3:       OK
        450  ns ±  21 ns, 0.67x
      Sequential ST Median3or5:       OK
        439  ns ± 7.4 ns, 0.65x
      Sequential IO Median3or5:       OK
        439  ns ±  26 ns, 0.65x
      ParStrategies ST Median3or5:    OK
        460  ns ±  43 ns, 0.68x
      ParStrategies IO Median3or5:    OK
        454  ns ±  35 ns, 0.67x
      Threads IO Median3:             OK
        1.23 μs ± 103 ns, 1.83x
      Threads IO Median3or5:          OK
        1.22 μs ±  95 ns, 1.81x
      fallback heapsort:              OK
        911  ns ±  66 ns, 1.35x
    Sorting 10 random arrays of length 17 with few duplicates
      C++:                            OK
        688  ns ±  66 ns
      Sequential ST Median3:          OK
        561  ns ±  45 ns, 0.82x
      Sequential IO Median3:          OK
        566  ns ±  55 ns, 0.82x
      ParStrategies ST Median3:       OK
        690  ns ±  55 ns, 1.00x
      ParStrategies IO Median3:       OK
        679  ns ±  62 ns, 0.99x
      Sequential ST Median3or5:       OK
        588  ns ±  38 ns, 0.85x
      Sequential IO Median3or5:       OK
        590  ns ±  48 ns, 0.86x
      ParStrategies ST Median3or5:    OK
        646  ns ±  64 ns, 0.94x
      ParStrategies IO Median3or5:    OK
        645  ns ±  24 ns, 0.94x
      Threads IO Median3:             OK
        1.45 μs ± 133 ns, 2.11x
      Threads IO Median3or5:          OK
        1.40 μs ± 129 ns, 2.03x
      fallback heapsort:              OK
        989  ns ±  59 ns, 1.44x
    Sorting 10 random arrays of length 100 with few duplicates
      C++:                            OK
        4.48 μs ± 368 ns
      Sequential ST Median3:          OK
        5.05 μs ± 444 ns, 1.13x
      Sequential IO Median3:          OK
        5.02 μs ± 367 ns, 1.12x
      ParStrategies ST Median3:       OK
        5.49 μs ± 464 ns, 1.23x
      ParStrategies IO Median3:       OK
        5.72 μs ± 171 ns, 1.28x
      Sequential ST Median3or5:       OK
        4.86 μs ± 485 ns, 1.08x
      Sequential IO Median3or5:       OK
        5.20 μs ± 350 ns, 1.16x
      ParStrategies ST Median3or5:    OK
        5.62 μs ± 442 ns, 1.25x
      ParStrategies IO Median3or5:    OK
        5.64 μs ± 473 ns, 1.26x
      Threads IO Median3:             OK
        6.15 μs ± 413 ns, 1.37x
      Threads IO Median3or5:          OK
        6.27 μs ± 217 ns, 1.40x
      fallback heapsort:              OK
        8.02 μs ± 409 ns, 1.79x
    Sorting 10 random arrays of length 256 with few duplicates
      C++:                            OK
        14.9 μs ± 1.2 μs
      Sequential ST Median3:          OK
        16.5 μs ± 1.4 μs, 1.11x
      Sequential IO Median3:          OK
        16.5 μs ± 1.6 μs, 1.11x
      ParStrategies ST Median3:       OK
        17.4 μs ± 1.4 μs, 1.17x
      ParStrategies IO Median3:       OK
        18.1 μs ± 1.7 μs, 1.22x
      Sequential ST Median3or5:       OK
        15.6 μs ± 1.4 μs, 1.05x
      Sequential IO Median3or5:       OK
        16.4 μs ± 1.5 μs, 1.10x
      ParStrategies ST Median3or5:    OK
        17.4 μs ± 1.5 μs, 1.17x
      ParStrategies IO Median3or5:    OK
        18.2 μs ± 1.6 μs, 1.22x
      Threads IO Median3:             OK
        17.6 μs ± 1.7 μs, 1.18x
      Threads IO Median3or5:          OK
        18.1 μs ± 1.4 μs, 1.21x
      fallback heapsort:              OK
        24.8 μs ± 1.5 μs, 1.67x
    Sorting 10 random arrays of length 1,000 with few duplicates
      C++:                            OK
        109  μs ± 5.4 μs
      Sequential ST Median3:          OK
        89.8 μs ± 2.7 μs, 0.83x
      Sequential IO Median3:          OK
        131  μs ± 7.5 μs, 1.21x
      ParStrategies ST Median3:       OK
        125  μs ±  11 μs, 1.15x
      ParStrategies IO Median3:       OK
        163  μs ±  15 μs, 1.50x
      Sequential ST Median3or5:       OK
        120  μs ± 2.6 μs, 1.10x
      Sequential IO Median3or5:       OK
        118  μs ± 4.2 μs, 1.09x
      ParStrategies ST Median3or5:    OK
        132  μs ± 6.4 μs, 1.22x
      ParStrategies IO Median3or5:    OK
        181  μs ±  18 μs, 1.67x
      Threads IO Median3:             OK
        126  μs ± 7.8 μs, 1.16x
      Threads IO Median3or5:          OK
        133  μs ±  11 μs, 1.23x
      fallback heapsort:              OK
        360  μs ±  26 μs, 3.31x
    Sorting 10 random arrays of length 10,000 with few duplicates
      C++:                            OK
        3.02 ms ± 170 μs
      Sequential ST Median3:          OK
        3.69 ms ± 337 μs, 1.22x
      Sequential IO Median3:          OK
        3.64 ms ± 356 μs, 1.21x
      ParStrategies ST Median3:       OK
        3.73 ms ± 336 μs, 1.23x
      ParStrategies IO Median3:       OK
        3.87 ms ± 354 μs, 1.28x
      Sequential ST Median3or5:       OK
        3.63 ms ± 350 μs, 1.20x
      Sequential IO Median3or5:       OK
        3.64 ms ± 350 μs, 1.20x
      ParStrategies ST Median3or5:    OK
        3.76 ms ± 336 μs, 1.24x
      ParStrategies IO Median3or5:    OK
        3.80 ms ± 367 μs, 1.26x
      Threads IO Median3:             OK
        3.67 ms ± 339 μs, 1.21x
      Threads IO Median3or5:          OK
        3.68 ms ± 358 μs, 1.22x
      fallback heapsort:              OK
        5.09 ms ± 391 μs, 1.68x
    Sorting 10 random arrays of length 100,000 with few duplicates
      C++:                            OK
        36.8 ms ± 1.6 ms
      Sequential ST Median3:          OK
        45.3 ms ± 3.4 ms, 1.23x
      Sequential IO Median3:          OK
        44.6 ms ± 2.8 ms, 1.21x
      ParStrategies ST Median3:       OK
        39.3 ms ± 2.6 ms, 1.07x
      ParStrategies IO Median3:       OK
        42.4 ms ± 3.8 ms, 1.15x
      Sequential ST Median3or5:       OK
        44.3 ms ± 2.7 ms, 1.20x
      Sequential IO Median3or5:       OK
        44.4 ms ± 2.8 ms, 1.21x
      ParStrategies ST Median3or5:    OK
        42.5 ms ± 3.5 ms, 1.15x
      ParStrategies IO Median3or5:    OK
        42.0 ms ± 2.7 ms, 1.14x
      Threads IO Median3:             OK
        27.6 ms ± 1.8 ms, 0.75x
      Threads IO Median3or5:          OK
        27.1 ms ± 2.1 ms, 0.74x
      fallback heapsort:              OK
        65.0 ms ± 2.9 ms, 1.77x
    Sorting 10 random arrays of length 1,000,000 with few duplicates
      C++:                            OK
        449  ms ±  35 ms
      Sequential ST Median3:          OK
        544  ms ±  11 ms, 1.21x
      Sequential IO Median3:          OK
        540  ms ±  11 ms, 1.20x
      ParStrategies ST Median3:       OK
        191  ms ±  15 ms, 0.42x
      ParStrategies IO Median3:       OK
        193  ms ±  10 ms, 0.43x
      Sequential ST Median3or5:       OK
        535  ms ±  11 ms, 1.19x
      Sequential IO Median3or5:       OK
        537  ms ± 8.4 ms, 1.20x
      ParStrategies ST Median3or5:    OK
        190  ms ±  12 ms, 0.42x
      ParStrategies IO Median3or5:    OK
        197  ms ±  20 ms, 0.44x
      Threads IO Median3:             OK
        249  ms ±  16 ms, 0.55x
      Threads IO Median3or5:          OK
        245  ms ±  13 ms, 0.55x
      fallback heapsort:              OK
        851  ms ±  30 ms, 1.90x
    Sorting 10 random arrays of length 16 with many duplicates
      C++:                            OK
        690  ns ±  22 ns
      Sequential ST Median3:          OK
        452  ns ±  33 ns, 0.66x
      Sequential IO Median3:          OK
        446  ns ±  43 ns, 0.65x
      ParStrategies ST Median3:       OK
        450  ns ±  42 ns, 0.65x
      ParStrategies IO Median3:       OK
        457  ns ±  29 ns, 0.66x
      Sequential ST Median3or5:       OK
        442  ns ±  42 ns, 0.64x
      Sequential IO Median3or5:       OK
        443  ns ±  42 ns, 0.64x
      ParStrategies ST Median3or5:    OK
        458  ns ±  45 ns, 0.66x
      ParStrategies IO Median3or5:    OK
        459  ns ±  43 ns, 0.67x
      Threads IO Median3:             OK
        1.23 μs ± 109 ns, 1.79x
      Threads IO Median3or5:          OK
        1.22 μs ±  92 ns, 1.77x
      fallback heapsort:              OK
        904  ns ±  52 ns, 1.31x
    Sorting 10 random arrays of length 17 with many duplicates
      C++:                            OK
        689  ns ±  57 ns
      Sequential ST Median3:          OK
        593  ns ±  28 ns, 0.86x
      Sequential IO Median3:          OK
        603  ns ±  41 ns, 0.87x
      ParStrategies ST Median3:       OK
        656  ns ±  48 ns, 0.95x
      ParStrategies IO Median3:       OK
        724  ns ±  59 ns, 1.05x
      Sequential ST Median3or5:       OK
        599  ns ±  53 ns, 0.87x
      Sequential IO Median3or5:       OK
        606  ns ±  51 ns, 0.88x
      ParStrategies ST Median3or5:    OK
        657  ns ±  46 ns, 0.95x
      ParStrategies IO Median3or5:    OK
        664  ns ±  44 ns, 0.96x
      Threads IO Median3:             OK
        1.40 μs ±  92 ns, 2.02x
      Threads IO Median3or5:          OK
        1.39 μs ±  85 ns, 2.02x
      fallback heapsort:              OK
        985  ns ±  51 ns, 1.43x
    Sorting 10 random arrays of length 100 with many duplicates
      C++:                            OK
        4.31 μs ± 357 ns
      Sequential ST Median3:          OK
        4.93 μs ± 361 ns, 1.15x
      Sequential IO Median3:          OK
        4.94 μs ± 390 ns, 1.15x
      ParStrategies ST Median3:       OK
        5.27 μs ± 416 ns, 1.22x
      ParStrategies IO Median3:       OK
        5.47 μs ± 363 ns, 1.27x
      Sequential ST Median3or5:       OK
        4.61 μs ± 436 ns, 1.07x
      Sequential IO Median3or5:       OK
        4.93 μs ± 419 ns, 1.15x
      ParStrategies ST Median3or5:    OK
        5.33 μs ± 329 ns, 1.24x
      ParStrategies IO Median3or5:    OK
        5.45 μs ± 352 ns, 1.27x
      Threads IO Median3:             OK
        5.79 μs ± 360 ns, 1.34x
      Threads IO Median3or5:          OK
        5.87 μs ± 384 ns, 1.36x
      fallback heapsort:              OK
        8.00 μs ± 331 ns, 1.86x
    Sorting 10 random arrays of length 256 with many duplicates
      C++:                            OK
        15.1 μs ± 1.2 μs
      Sequential ST Median3:          OK
        16.9 μs ± 1.7 μs, 1.12x
      Sequential IO Median3:          OK
        17.0 μs ± 1.5 μs, 1.13x
      ParStrategies ST Median3:       OK
        17.9 μs ± 795 ns, 1.19x
      ParStrategies IO Median3:       OK
        18.4 μs ± 1.6 μs, 1.22x
      Sequential ST Median3or5:       OK
        15.6 μs ± 1.4 μs, 1.04x
      Sequential IO Median3or5:       OK
        16.7 μs ± 1.4 μs, 1.11x
      ParStrategies ST Median3or5:    OK
        17.8 μs ± 1.7 μs, 1.18x
      ParStrategies IO Median3or5:    OK
        18.6 μs ± 1.6 μs, 1.24x
      Threads IO Median3:             OK
        17.9 μs ± 670 ns, 1.19x
      Threads IO Median3or5:          OK
        18.7 μs ± 1.6 μs, 1.24x
      fallback heapsort:              OK
        24.9 μs ± 1.3 μs, 1.65x
    Sorting 10 random arrays of length 1,000 with many duplicates
      C++:                            OK
        60.7 μs ± 1.3 μs
      Sequential ST Median3:          OK
        162  μs ± 3.1 μs, 2.67x
      Sequential IO Median3:          OK
        130  μs ± 4.7 μs, 2.13x
      ParStrategies ST Median3:       OK
        179  μs ± 7.1 μs, 2.94x
      ParStrategies IO Median3:       OK
        159  μs ± 3.8 μs, 2.62x
      Sequential ST Median3or5:       OK
        126  μs ±  12 μs, 2.07x
      Sequential IO Median3or5:       OK
        139  μs ± 7.3 μs, 2.29x
      ParStrategies ST Median3or5:    OK
        127  μs ± 8.9 μs, 2.09x
      ParStrategies IO Median3or5:    OK
        151  μs ± 6.1 μs, 2.49x
      Threads IO Median3:             OK
        86.0 μs ± 5.6 μs, 1.42x
      Threads IO Median3or5:          OK
        83.4 μs ± 7.7 μs, 1.37x
      fallback heapsort:              OK
        352  μs ±  25 μs, 5.80x
    Sorting 10 random arrays of length 10,000 with many duplicates
      C++:                            OK
        2.69 ms ± 173 μs
      Sequential ST Median3:          OK
        3.09 ms ± 276 μs, 1.15x
      Sequential IO Median3:          OK
        2.98 ms ± 190 μs, 1.11x
      ParStrategies ST Median3:       OK
        3.06 ms ± 212 μs, 1.14x
      ParStrategies IO Median3:       OK
        3.19 ms ± 186 μs, 1.19x
      Sequential ST Median3or5:       OK
        3.02 ms ± 191 μs, 1.12x
      Sequential IO Median3or5:       OK
        3.01 ms ± 186 μs, 1.12x
      ParStrategies ST Median3or5:    OK
        3.11 ms ± 187 μs, 1.16x
      ParStrategies IO Median3or5:    OK
        3.14 ms ± 192 μs, 1.17x
      Threads IO Median3:             OK
        3.05 ms ± 171 μs, 1.14x
      Threads IO Median3or5:          OK
        3.08 ms ± 270 μs, 1.15x
      fallback heapsort:              OK
        4.97 ms ± 337 μs, 1.85x
    Sorting 10 random arrays of length 100,000 with many duplicates
      C++:                            OK
        26.6 ms ± 1.4 ms
      Sequential ST Median3:          OK
        27.7 ms ± 1.3 ms, 1.04x
      Sequential IO Median3:          OK
        27.2 ms ± 1.4 ms, 1.02x
      ParStrategies ST Median3:       OK
        26.0 ms ± 1.1 ms, 0.98x
      ParStrategies IO Median3:       OK
        27.2 ms ± 2.5 ms, 1.02x
      Sequential ST Median3or5:       OK
        27.1 ms ± 1.6 ms, 1.02x
      Sequential IO Median3or5:       OK
        27.6 ms ± 1.9 ms, 1.04x
      ParStrategies ST Median3or5:    OK
        26.7 ms ± 2.1 ms, 1.00x
      ParStrategies IO Median3or5:    OK
        26.2 ms ± 2.1 ms, 0.98x
      Threads IO Median3:             OK
        18.2 ms ± 900 μs, 0.68x
      Threads IO Median3or5:          OK
        17.9 ms ± 1.3 ms, 0.67x
      fallback heapsort:              OK
        64.5 ms ± 2.8 ms, 2.42x
    Sorting 10 random arrays of length 1,000,000 with many duplicates
      C++:                            OK
        281  ms ±  25 ms
      Sequential ST Median3:          OK
        274  ms ± 2.9 ms, 0.98x
      Sequential IO Median3:          OK
        269  ms ± 5.3 ms, 0.96x
      ParStrategies ST Median3:       OK
        189  ms ± 8.9 ms, 0.67x
      ParStrategies IO Median3:       OK
        194  ms ±  11 ms, 0.69x
      Sequential ST Median3or5:       OK
        263  ms ± 3.2 ms, 0.94x
      Sequential IO Median3or5:       OK
        266  ms ± 2.9 ms, 0.95x
      ParStrategies ST Median3or5:    OK
        188  ms ±  14 ms, 0.67x
      ParStrategies IO Median3or5:    OK
        194  ms ±  11 ms, 0.69x
      Threads IO Median3:             OK
        151  ms ± 7.5 ms, 0.54x
      Threads IO Median3or5:          OK
        147  ms ±  12 ms, 0.53x
      fallback heapsort:              OK
        784  ms ±  11 ms, 2.79x
  (Double, Double, Int64)
    Sorting 10 random arrays of length 16 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        841  ns ±  57 ns
      C++ three vectors:              OK
        2.35 μs ± 176 ns
      Sequential ST Median3 Unbox:    OK
        1.34 μs ± 128 ns
      Sequential ST Median3or5 Unbox: OK
        1.36 μs ±  91 ns
      Sequential ST Median3 Prim:     OK
        1.23 μs ± 103 ns
      Sequential ST Median3or5 Prim:  OK
        1.22 μs ± 112 ns
    Sorting 10 random arrays of length 17 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        901  ns ±  26 ns
      C++ three vectors:              OK
        2.60 μs ± 207 ns
      Sequential ST Median3 Unbox:    OK
        1.59 μs ± 126 ns
      Sequential ST Median3or5 Unbox: OK
        1.70 μs ± 167 ns
      Sequential ST Median3 Prim:     OK
        1.44 μs ± 103 ns
      Sequential ST Median3or5 Prim:  OK
        1.46 μs ± 113 ns
    Sorting 10 random arrays of length 100 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        7.72 μs ± 581 ns
      C++ three vectors:              OK
        14.5 μs ± 1.1 μs
      Sequential ST Median3 Unbox:    OK
        10.4 μs ± 959 ns
      Sequential ST Median3or5 Unbox: OK
        10.2 μs ± 745 ns
      Sequential ST Median3 Prim:     OK
        12.3 μs ± 809 ns
      Sequential ST Median3or5 Prim:  OK
        12.5 μs ± 795 ns
    Sorting 10 random arrays of length 256 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        14.6 μs ± 682 ns
      C++ three vectors:              OK
        42.7 μs ± 4.2 μs
      Sequential ST Median3 Unbox:    OK
        34.3 μs ± 1.7 μs
      Sequential ST Median3or5 Unbox: OK
        33.5 μs ± 1.4 μs
      Sequential ST Median3 Prim:     OK
        30.7 μs ± 2.6 μs
      Sequential ST Median3or5 Prim:  OK
        32.0 μs ± 2.1 μs
    Sorting 10 random arrays of length 1,000 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        69.4 μs ± 4.4 μs
      C++ three vectors:              OK
        212  μs ±  16 μs
      Sequential ST Median3 Unbox:    OK
        265  μs ±  23 μs
      Sequential ST Median3or5 Unbox: OK
        294  μs ±  26 μs
      Sequential ST Median3 Prim:     OK
        299  μs ±  27 μs
      Sequential ST Median3or5 Prim:  OK
        305  μs ±  23 μs
    Sorting 10 random arrays of length 10,000 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        3.27 ms ± 195 μs
      C++ three vectors:              OK
        3.62 ms ± 352 μs
      Sequential ST Median3 Unbox:    OK
        5.11 ms ± 338 μs
      Sequential ST Median3or5 Unbox: OK
        5.17 ms ± 398 μs
      Sequential ST Median3 Prim:     OK
        5.70 ms ± 369 μs
      Sequential ST Median3or5 Prim:  OK
        5.64 ms ± 370 μs
    Sorting 10 random arrays of length 100,000 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        40.7 ms ± 1.6 ms
      C++ three vectors:              OK
        43.8 ms ± 1.4 ms
      Sequential ST Median3 Unbox:    OK
        62.2 ms ± 2.7 ms
      Sequential ST Median3or5 Unbox: OK
        62.9 ms ± 3.0 ms
      Sequential ST Median3 Prim:     OK
        70.7 ms ± 1.8 ms
      Sequential ST Median3or5 Prim:  OK
        69.7 ms ± 3.4 ms
    Sorting 10 random arrays of length 1,000,000 with few duplicates
      Sanity:                         OK
      C++ single vector:              OK
        510  ms ± 3.0 ms
      C++ three vectors:              OK
        542  ms ±  18 ms
      Sequential ST Median3 Unbox:    OK
        752  ms ±  14 ms
      Sequential ST Median3or5 Unbox: OK
        757  ms ±  35 ms
      Sequential ST Median3 Prim:     OK
        848  ms ±  73 ms
      Sequential ST Median3or5 Prim:  OK
        823  ms ±  20 ms
    Sorting 10 random arrays of length 16 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        876  ns ±  54 ns
      C++ three vectors:              OK
        2.40 μs ± 181 ns
      Sequential ST Median3 Unbox:    OK
        1.45 μs ± 132 ns
      Sequential ST Median3or5 Unbox: OK
        1.44 μs ± 115 ns
      Sequential ST Median3 Prim:     OK
        1.39 μs ± 102 ns
      Sequential ST Median3or5 Prim:  OK
        1.41 μs ±  94 ns
    Sorting 10 random arrays of length 17 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        889  ns ±  57 ns
      C++ three vectors:              OK
        2.63 μs ± 181 ns
      Sequential ST Median3 Unbox:    OK
        1.64 μs ± 120 ns
      Sequential ST Median3or5 Unbox: OK
        1.65 μs ± 130 ns
      Sequential ST Median3 Prim:     OK
        1.47 μs ± 107 ns
      Sequential ST Median3or5 Prim:  OK
        1.47 μs ± 119 ns
    Sorting 10 random arrays of length 100 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        7.62 μs ± 597 ns
      C++ three vectors:              OK
        13.8 μs ± 693 ns
      Sequential ST Median3 Unbox:    OK
        10.8 μs ± 790 ns
      Sequential ST Median3or5 Unbox: OK
        10.5 μs ± 839 ns
      Sequential ST Median3 Prim:     OK
        12.7 μs ± 814 ns
      Sequential ST Median3or5 Prim:  OK
        12.9 μs ± 910 ns
    Sorting 10 random arrays of length 256 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        14.8 μs ± 978 ns
      C++ three vectors:              OK
        38.7 μs ± 2.7 μs
      Sequential ST Median3 Unbox:    OK
        34.0 μs ± 3.4 μs
      Sequential ST Median3or5 Unbox: OK
        34.0 μs ± 3.0 μs
      Sequential ST Median3 Prim:     OK
        31.6 μs ± 3.1 μs
      Sequential ST Median3or5 Prim:  OK
        32.5 μs ± 2.3 μs
    Sorting 10 random arrays of length 1,000 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        69.2 μs ± 4.9 μs
      C++ three vectors:              OK
        151  μs ±  11 μs
      Sequential ST Median3 Unbox:    OK
        256  μs ±  17 μs
      Sequential ST Median3or5 Unbox: OK
        291  μs ±  15 μs
      Sequential ST Median3 Prim:     OK
        303  μs ±  26 μs
      Sequential ST Median3or5 Prim:  OK
        292  μs ± 7.8 μs
    Sorting 10 random arrays of length 10,000 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        2.98 ms ± 193 μs
      C++ three vectors:              OK
        3.48 ms ± 182 μs
      Sequential ST Median3 Unbox:    OK
        4.30 ms ± 345 μs
      Sequential ST Median3or5 Unbox: OK
        4.50 ms ± 446 μs
      Sequential ST Median3 Prim:     OK
        4.80 ms ± 339 μs
      Sequential ST Median3or5 Prim:  OK
        4.87 ms ± 407 μs
    Sorting 10 random arrays of length 100,000 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        30.2 ms ± 1.8 ms
      C++ three vectors:              OK
        41.1 ms ± 1.8 ms
      Sequential ST Median3 Unbox:    OK
        40.8 ms ± 1.9 ms
      Sequential ST Median3or5 Unbox: OK
        41.6 ms ± 1.7 ms
      Sequential ST Median3 Prim:     OK
        43.7 ms ± 1.5 ms
      Sequential ST Median3or5 Prim:  OK
        43.6 ms ± 3.0 ms
    Sorting 10 random arrays of length 1,000,000 with many duplicates
      Sanity:                         OK
      C++ single vector:              OK
        337  ms ±  11 ms
      C++ three vectors:              OK
        420  ms ± 5.0 ms
      Sequential ST Median3 Unbox:    OK
        389  ms ± 3.3 ms
      Sequential ST Median3or5 Unbox: OK
        398  ms ± 3.4 ms
      Sequential ST Median3 Prim:     OK
        452  ms ±  27 ms
      Sequential ST Median3or5 Prim:  OK
        428  ms ± 2.9 ms