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.
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)).
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: Intel i5-9600K CPU @ 3.70GHz, 6 cores, no hyperthreading, GHC 9.6.1.
The default sort exported in Data.Vector.Algorithms.Quicksort is Sequential and Median3or5.
$ cabal run bench -- -j1 --time-mode wall --timeout 300
All
Sorting fuzzy matching scores vector
C++: OK (0.54s)
377 μs ± 30 μs
Sequential ST Median3: OK (0.36s)
315 μs ± 17 μs, 0.83x
Sequential IO Median3: OK (0.31s)
288 μs ± 17 μs, 0.76x
ParStrategies ST Median3: OK (0.15s)
285 μs ± 23 μs, 0.76x
ParStrategies IO Median3: OK (0.16s)
306 μs ± 22 μs, 0.81x
Sequential ST Median3or5: OK (0.28s)
261 μs ± 13 μs, 0.69x
Sequential IO Median3or5: OK (0.28s)
264 μs ± 25 μs, 0.70x
ParStrategies ST Median3or5: OK (0.14s)
268 μs ± 21 μs, 0.71x
ParStrategies IO Median3or5: OK (0.15s)
272 μs ± 27 μs, 0.72x
Sequential ST AveragingMedian: OK (0.16s)
2.47 ms ± 191 μs, 6.55x
Threads IO Median3: OK (0.31s)
295 μs ± 28 μs, 0.78x
Threads IO Median3or5: OK (0.24s)
230 μs ± 12 μs, 0.61x
vector-algorithms heapsort: OK (0.27s)
2.06 ms ± 97 μs, 5.45x
fallback heapsort: OK (0.25s)
1.91 ms ± 106 μs, 5.07x
Sorting 10 random arrays of length 16 with few duplicates
C++: OK (0.36s)
654 ns ± 24 ns
Sequential ST Median3: OK (0.31s)
554 ns ± 23 ns, 0.85x
Sequential IO Median3: OK (0.16s)
559 ns ± 44 ns, 0.85x
ParStrategies ST Median3: OK (0.16s)
578 ns ± 58 ns, 0.88x
ParStrategies IO Median3: OK (0.32s)
578 ns ± 26 ns, 0.88x
Sequential ST Median3or5: OK (0.16s)
569 ns ± 50 ns, 0.87x
Sequential IO Median3or5: OK (0.16s)
571 ns ± 50 ns, 0.87x
ParStrategies ST Median3or5: OK (0.17s)
580 ns ± 42 ns, 0.89x
ParStrategies IO Median3or5: OK (0.16s)
577 ns ± 49 ns, 0.88x
Sequential ST AveragingMedian: OK (0.31s)
557 ns ± 27 ns, 0.85x
Threads IO Median3: OK (0.24s)
1.71 μs ± 128 ns, 2.62x
Threads IO Median3or5: OK (0.24s)
1.73 μs ± 120 ns, 2.64x
vector-algorithms heapsort: OK (0.20s)
1.41 μs ± 117 ns, 2.16x
fallback heapsort: OK (0.62s)
1.15 μs ± 29 ns, 1.76x
Sorting 10 random arrays of length 17 with few duplicates
C++: OK (0.21s)
758 ns ± 73 ns
Sequential ST Median3: OK (0.38s)
701 ns ± 35 ns, 0.92x
Sequential IO Median3: OK (0.20s)
728 ns ± 60 ns, 0.96x
ParStrategies ST Median3: OK (0.22s)
773 ns ± 49 ns, 1.02x
ParStrategies IO Median3: OK (0.21s)
766 ns ± 44 ns, 1.01x
Sequential ST Median3or5: OK (0.39s)
727 ns ± 55 ns, 0.96x
Sequential IO Median3or5: OK (0.20s)
724 ns ± 47 ns, 0.95x
ParStrategies ST Median3or5: OK (0.22s)
793 ns ± 68 ns, 1.05x
ParStrategies IO Median3or5: OK (0.22s)
791 ns ± 63 ns, 1.04x
Sequential ST AveragingMedian: OK (0.30s)
2.18 μs ± 92 ns, 2.88x
Threads IO Median3: OK (0.14s)
1.89 μs ± 182 ns, 2.49x
Threads IO Median3or5: OK (0.14s)
1.99 μs ± 176 ns, 2.63x
vector-algorithms heapsort: OK (0.21s)
1.52 μs ± 114 ns, 2.01x
fallback heapsort: OK (0.18s)
1.23 μs ± 116 ns, 1.62x
Sorting 10 random arrays of length 100 with few duplicates
C++: OK (0.16s)
4.33 μs ± 413 ns
Sequential ST Median3: OK (0.38s)
5.56 μs ± 371 ns, 1.29x
Sequential IO Median3: OK (0.20s)
5.55 μs ± 333 ns, 1.28x
ParStrategies ST Median3: OK (0.21s)
6.03 μs ± 345 ns, 1.39x
ParStrategies IO Median3: OK (0.50s)
7.24 μs ± 287 ns, 1.67x
Sequential ST Median3or5: OK (0.20s)
5.57 μs ± 337 ns, 1.29x
Sequential IO Median3or5: OK (0.20s)
5.59 μs ± 329 ns, 1.29x
ParStrategies ST Median3or5: OK (0.22s)
6.28 μs ± 371 ns, 1.45x
ParStrategies IO Median3or5: OK (0.22s)
6.52 μs ± 621 ns, 1.51x
Sequential ST AveragingMedian: OK (0.26s)
30.5 μs ± 2.8 μs, 7.05x
Threads IO Median3: OK (0.13s)
7.28 μs ± 686 ns, 1.68x
Threads IO Median3or5: OK (0.49s)
7.22 μs ± 296 ns, 1.67x
vector-algorithms heapsort: OK (0.32s)
18.8 μs ± 1.4 μs, 4.35x
fallback heapsort: OK (0.20s)
22.9 μs ± 1.5 μs, 5.30x
Sorting 10 random arrays of length 256 with few duplicates
C++: OK (0.19s)
44.7 μs ± 2.9 μs
Sequential ST Median3: OK (0.45s)
54.6 μs ± 2.8 μs, 1.22x
Sequential IO Median3: OK (0.20s)
46.9 μs ± 3.5 μs, 1.05x
ParStrategies ST Median3: OK (0.22s)
51.3 μs ± 3.9 μs, 1.15x
ParStrategies IO Median3: OK (0.23s)
53.7 μs ± 4.1 μs, 1.20x
Sequential ST Median3or5: OK (0.21s)
48.1 μs ± 3.1 μs, 1.07x
Sequential IO Median3or5: OK (0.21s)
47.8 μs ± 2.9 μs, 1.07x
ParStrategies ST Median3or5: OK (0.23s)
54.0 μs ± 4.0 μs, 1.21x
ParStrategies IO Median3or5: OK (0.24s)
54.3 μs ± 5.0 μs, 1.21x
Sequential ST AveragingMedian: OK (0.13s)
119 μs ± 11 μs, 2.67x
Threads IO Median3: OK (0.24s)
56.3 μs ± 5.6 μs, 1.26x
Threads IO Median3or5: OK (0.24s)
56.1 μs ± 4.6 μs, 1.25x
vector-algorithms heapsort: OK (0.23s)
110 μs ± 6.6 μs, 2.47x
fallback heapsort: OK (0.21s)
95.2 μs ± 6.5 μs, 2.13x
Sorting 10 random arrays of length 1,000 with few duplicates
C++: OK (0.15s)
274 μs ± 24 μs
Sequential ST Median3: OK (0.13s)
471 μs ± 46 μs, 1.72x
Sequential IO Median3: OK (0.23s)
428 μs ± 28 μs, 1.56x
ParStrategies ST Median3: OK (0.19s)
350 μs ± 27 μs, 1.27x
ParStrategies IO Median3: OK (0.24s)
451 μs ± 42 μs, 1.65x
Sequential ST Median3or5: OK (0.18s)
333 μs ± 31 μs, 1.22x
Sequential IO Median3or5: OK (0.12s)
428 μs ± 42 μs, 1.56x
ParStrategies ST Median3or5: OK (0.25s)
460 μs ± 42 μs, 1.68x
ParStrategies IO Median3or5: OK (0.19s)
363 μs ± 27 μs, 1.32x
Sequential ST AveragingMedian: OK (0.20s)
742 μs ± 64 μs, 2.71x
Threads IO Median3: OK (0.25s)
469 μs ± 25 μs, 1.71x
Threads IO Median3or5: OK (0.25s)
457 μs ± 37 μs, 1.67x
vector-algorithms heapsort: OK (0.18s)
667 μs ± 65 μs, 2.43x
fallback heapsort: OK (0.17s)
618 μs ± 46 μs, 2.25x
Sorting 10 random arrays of length 10,000 with few duplicates
C++: OK (0.29s)
4.50 ms ± 269 μs
Sequential ST Median3: OK (0.19s)
6.00 ms ± 586 μs, 1.33x
Sequential IO Median3: OK (0.28s)
4.31 ms ± 260 μs, 0.96x
ParStrategies ST Median3: OK (0.18s)
5.73 ms ± 514 μs, 1.27x
ParStrategies IO Median3: OK (0.20s)
6.06 ms ± 375 μs, 1.35x
Sequential ST Median3or5: OK (0.14s)
4.35 ms ± 353 μs, 0.97x
Sequential IO Median3or5: OK (0.18s)
5.57 ms ± 524 μs, 1.24x
ParStrategies ST Median3or5: OK (0.15s)
4.62 ms ± 340 μs, 1.03x
ParStrategies IO Median3or5: OK (0.38s)
5.89 ms ± 520 μs, 1.31x
Sequential ST AveragingMedian: OK (0.31s)
9.89 ms ± 437 μs, 2.20x
Threads IO Median3: OK (0.60s)
4.65 ms ± 291 μs, 1.03x
Threads IO Median3or5: OK (0.37s)
5.77 ms ± 183 μs, 1.28x
vector-algorithms heapsort: OK (0.14s)
8.79 ms ± 718 μs, 1.95x
fallback heapsort: OK (0.26s)
8.34 ms ± 568 μs, 1.85x
Sorting 10 random arrays of length 100,000 with few duplicates
C++: OK (0.17s)
55.6 ms ± 3.2 ms
Sequential ST Median3: OK (0.24s)
78.1 ms ± 3.7 ms, 1.41x
Sequential IO Median3: OK (0.21s)
69.3 ms ± 3.7 ms, 1.25x
ParStrategies ST Median3: OK (0.18s)
59.5 ms ± 4.5 ms, 1.07x
ParStrategies IO Median3: OK (3.66s)
56.6 ms ± 5.3 ms, 1.02x
Sequential ST Median3or5: OK (0.16s)
54.0 ms ± 3.5 ms, 0.97x
Sequential IO Median3or5: OK (0.21s)
67.3 ms ± 5.7 ms, 1.21x
ParStrategies ST Median3or5: OK (0.19s)
62.3 ms ± 5.6 ms, 1.12x
ParStrategies IO Median3or5: OK (0.45s)
65.3 ms ± 4.7 ms, 1.17x
Sequential ST AveragingMedian: OK (0.38s)
127 ms ± 4.5 ms, 2.28x
Threads IO Median3: OK (0.34s)
48.3 ms ± 2.7 ms, 0.87x
Threads IO Median3or5: OK (0.34s)
47.7 ms ± 2.4 ms, 0.86x
vector-algorithms heapsort: OK (0.37s)
124 ms ± 8.9 ms, 2.23x
fallback heapsort: OK (0.81s)
113 ms ± 5.4 ms, 2.04x
Sorting 10 random arrays of length 1,000,000 with few duplicates
C++: OK (2.05s)
682 ms ± 15 ms
Sequential ST Median3: OK (2.18s)
727 ms ± 7.5 ms, 1.06x
Sequential IO Median3: OK (2.44s)
812 ms ± 9.6 ms, 1.19x
ParStrategies ST Median3: OK (1.44s)
204 ms ± 13 ms, 0.30x
ParStrategies IO Median3: OK (0.81s)
268 ms ± 20 ms, 0.39x
Sequential ST Median3or5: OK (2.00s)
664 ms ± 45 ms, 0.97x
Sequential IO Median3or5: OK (1.95s)
645 ms ± 43 ms, 0.95x
ParStrategies ST Median3or5: OK (1.49s)
209 ms ± 4.9 ms, 0.31x
ParStrategies IO Median3or5: OK (1.46s)
208 ms ± 21 ms, 0.30x
Sequential ST AveragingMedian: OK (4.05s)
1.348 s ± 8.5 ms, 1.98x
Threads IO Median3: OK (1.53s)
508 ms ± 7.1 ms, 0.74x
Threads IO Median3or5: OK (1.36s)
452 ms ± 6.2 ms, 0.66x
vector-algorithms heapsort: OK (3.94s)
1.309 s ± 53 ms, 1.92x
fallback heapsort: OK (3.67s)
1.220 s ± 27 ms, 1.79x
Sorting 10 random arrays of length 10,000,000 with few duplicates
C++: OK (18.62s)
6.188 s ± 240 ms
Sequential ST Median3: OK (25.26s)
8.422 s ± 49 ms, 1.36x
Sequential IO Median3: OK (21.91s)
7.295 s ± 118 ms, 1.18x
ParStrategies ST Median3: OK (6.01s)
2.010 s ± 110 ms, 0.32x
ParStrategies IO Median3: OK (6.16s)
2.044 s ± 100 ms, 0.33x
Sequential ST Median3or5: OK (21.85s)
7.284 s ± 4.9 ms, 1.18x
Sequential IO Median3or5: OK (21.94s)
7.311 s ± 38 ms, 1.18x
ParStrategies ST Median3or5: OK (6.05s)
2.010 s ± 72 ms, 0.32x
ParStrategies IO Median3or5: OK (6.27s)
2.090 s ± 2.8 ms, 0.34x
Sequential ST AveragingMedian: OK (81.58s)
27.074 s ± 1.60 s, 4.38x
Threads IO Median3: OK (15.86s)
5.283 s ± 29 ms, 0.85x
Threads IO Median3or5: OK (12.85s)
4.283 s ± 7.3 ms, 0.69x
vector-algorithms heapsort: OK (71.14s)
23.711 s ± 33 ms, 3.83x
fallback heapsort: OK (96.39s)
32.157 s ± 355 ms, 5.20x
Sorting 10 random arrays of length 16 with many duplicates
C++: OK (0.37s)
673 ns ± 36 ns
Sequential ST Median3: OK (0.17s)
576 ns ± 53 ns, 0.86x
Sequential IO Median3: OK (0.16s)
560 ns ± 49 ns, 0.83x
ParStrategies ST Median3: OK (0.17s)
576 ns ± 49 ns, 0.86x
ParStrategies IO Median3: OK (0.17s)
575 ns ± 42 ns, 0.85x
Sequential ST Median3or5: OK (0.17s)
575 ns ± 57 ns, 0.85x
Sequential IO Median3or5: OK (0.17s)
568 ns ± 47 ns, 0.84x
ParStrategies ST Median3or5: OK (0.33s)
596 ns ± 50 ns, 0.89x
ParStrategies IO Median3or5: OK (0.33s)
593 ns ± 30 ns, 0.88x
Sequential ST AveragingMedian: OK (0.32s)
571 ns ± 26 ns, 0.85x
Threads IO Median3: OK (0.24s)
1.71 μs ± 85 ns, 2.54x
Threads IO Median3or5: OK (0.24s)
1.71 μs ± 118 ns, 2.53x
vector-algorithms heapsort: OK (0.20s)
1.39 μs ± 90 ns, 2.06x
fallback heapsort: OK (0.17s)
1.17 μs ± 83 ns, 1.73x
Sorting 10 random arrays of length 17 with many duplicates
C++: OK (0.22s)
763 ns ± 56 ns
Sequential ST Median3: OK (0.41s)
752 ns ± 22 ns, 0.99x
Sequential IO Median3: OK (0.21s)
744 ns ± 64 ns, 0.98x
ParStrategies ST Median3: OK (0.23s)
798 ns ± 44 ns, 1.05x
ParStrategies IO Median3: OK (0.22s)
782 ns ± 46 ns, 1.03x
Sequential ST Median3or5: OK (0.21s)
738 ns ± 44 ns, 0.97x
Sequential IO Median3or5: OK (0.21s)
749 ns ± 52 ns, 0.98x
ParStrategies ST Median3or5: OK (0.22s)
786 ns ± 42 ns, 1.03x
ParStrategies IO Median3or5: OK (0.44s)
796 ns ± 29 ns, 1.04x
Sequential ST AveragingMedian: OK (0.30s)
2.16 μs ± 88 ns, 2.83x
Threads IO Median3: OK (0.14s)
1.92 μs ± 173 ns, 2.51x
Threads IO Median3or5: OK (0.27s)
1.98 μs ± 116 ns, 2.59x
vector-algorithms heapsort: OK (0.22s)
1.52 μs ± 97 ns, 1.99x
fallback heapsort: OK (0.18s)
1.26 μs ± 85 ns, 1.65x
Sorting 10 random arrays of length 100 with many duplicates
C++: OK (0.19s)
5.12 μs ± 401 ns
Sequential ST Median3: OK (0.21s)
5.85 μs ± 409 ns, 1.14x
Sequential IO Median3: OK (0.21s)
5.85 μs ± 527 ns, 1.14x
ParStrategies ST Median3: OK (0.22s)
6.26 μs ± 395 ns, 1.22x
ParStrategies IO Median3: OK (0.28s)
7.89 μs ± 461 ns, 1.54x
Sequential ST Median3or5: OK (0.21s)
5.71 μs ± 458 ns, 1.11x
Sequential IO Median3or5: OK (0.20s)
5.70 μs ± 404 ns, 1.11x
ParStrategies ST Median3or5: OK (0.23s)
6.45 μs ± 381 ns, 1.26x
ParStrategies IO Median3or5: OK (0.23s)
6.47 μs ± 499 ns, 1.26x
Sequential ST AveragingMedian: OK (0.13s)
29.0 μs ± 2.6 μs, 5.65x
Threads IO Median3: OK (0.14s)
7.34 μs ± 671 ns, 1.43x
Threads IO Median3or5: OK (0.26s)
7.48 μs ± 455 ns, 1.46x
vector-algorithms heapsort: OK (0.17s)
18.6 μs ± 1.3 μs, 3.63x
fallback heapsort: OK (0.20s)
23.2 μs ± 2.2 μs, 4.52x
Sorting 10 random arrays of length 256 with many duplicates
C++: OK (0.20s)
46.3 μs ± 3.2 μs
Sequential ST Median3: OK (0.25s)
55.6 μs ± 5.0 μs, 1.20x
Sequential IO Median3: OK (0.42s)
49.5 μs ± 3.0 μs, 1.07x
ParStrategies ST Median3: OK (0.23s)
53.0 μs ± 2.7 μs, 1.14x
ParStrategies IO Median3: OK (0.13s)
55.7 μs ± 5.3 μs, 1.20x
Sequential ST Median3or5: OK (0.22s)
49.2 μs ± 2.9 μs, 1.06x
Sequential IO Median3or5: OK (0.42s)
49.3 μs ± 2.0 μs, 1.06x
ParStrategies ST Median3or5: OK (0.24s)
55.2 μs ± 4.2 μs, 1.19x
ParStrategies IO Median3or5: OK (0.47s)
55.0 μs ± 1.5 μs, 1.19x
Sequential ST AveragingMedian: OK (0.13s)
121 μs ± 11 μs, 2.60x
Threads IO Median3: OK (0.13s)
56.1 μs ± 5.4 μs, 1.21x
Threads IO Median3or5: OK (0.25s)
56.6 μs ± 3.4 μs, 1.22x
vector-algorithms heapsort: OK (0.22s)
102 μs ± 5.2 μs, 2.21x
fallback heapsort: OK (0.21s)
94.9 μs ± 5.4 μs, 2.05x
Sorting 10 random arrays of length 1,000 with many duplicates
C++: OK (0.30s)
279 μs ± 14 μs
Sequential ST Median3: OK (0.20s)
367 μs ± 22 μs, 1.31x
Sequential IO Median3: OK (0.18s)
335 μs ± 33 μs, 1.20x
ParStrategies ST Median3: OK (0.19s)
344 μs ± 22 μs, 1.23x
ParStrategies IO Median3: OK (0.19s)
359 μs ± 24 μs, 1.28x
Sequential ST Median3or5: OK (0.18s)
336 μs ± 25 μs, 1.20x
Sequential IO Median3or5: OK (0.18s)
336 μs ± 21 μs, 1.20x
ParStrategies ST Median3or5: OK (0.38s)
358 μs ± 14 μs, 1.28x
ParStrategies IO Median3or5: OK (0.19s)
363 μs ± 26 μs, 1.30x
Sequential ST AveragingMedian: OK (0.16s)
583 μs ± 43 μs, 2.09x
Threads IO Median3: OK (0.19s)
357 μs ± 23 μs, 1.28x
Threads IO Median3or5: OK (0.19s)
358 μs ± 28 μs, 1.28x
vector-algorithms heapsort: OK (0.15s)
536 μs ± 42 μs, 1.92x
fallback heapsort: OK (0.13s)
494 μs ± 46 μs, 1.77x
Sorting 10 random arrays of length 10,000 with many duplicates
C++: OK (0.21s)
3.25 ms ± 184 μs
Sequential ST Median3: OK (0.14s)
4.23 ms ± 347 μs, 1.30x
Sequential IO Median3: OK (0.24s)
3.65 ms ± 329 μs, 1.12x
ParStrategies ST Median3: OK (0.12s)
3.76 ms ± 362 μs, 1.15x
ParStrategies IO Median3: OK (0.13s)
3.98 ms ± 360 μs, 1.22x
Sequential ST Median3or5: OK (0.24s)
3.72 ms ± 254 μs, 1.14x
Sequential IO Median3or5: OK (0.12s)
3.71 ms ± 344 μs, 1.14x
ParStrategies ST Median3or5: OK (0.13s)
3.96 ms ± 344 μs, 1.22x
ParStrategies IO Median3or5: OK (0.27s)
4.10 ms ± 315 μs, 1.26x
Sequential ST AveragingMedian: OK (0.12s)
7.81 ms ± 724 μs, 2.40x
Threads IO Median3: OK (0.13s)
3.92 ms ± 338 μs, 1.20x
Threads IO Median3or5: OK (0.13s)
4.05 ms ± 347 μs, 1.24x
vector-algorithms heapsort: OK (0.12s)
7.85 ms ± 674 μs, 2.41x
fallback heapsort: OK (0.21s)
6.58 ms ± 434 μs, 2.02x
Sorting 10 random arrays of length 100,000 with many duplicates
C++: OK (0.24s)
33.0 ms ± 1.5 ms
Sequential ST Median3: OK (0.12s)
38.8 ms ± 2.7 ms, 1.18x
Sequential IO Median3: OK (0.10s)
33.1 ms ± 2.9 ms, 1.00x
ParStrategies ST Median3: OK (0.23s)
32.9 ms ± 1.9 ms, 1.00x
ParStrategies IO Median3: OK (0.13s)
41.5 ms ± 3.3 ms, 1.26x
Sequential ST Median3or5: OK (0.23s)
32.8 ms ± 2.3 ms, 1.00x
Sequential IO Median3or5: OK (0.10s)
33.4 ms ± 3.1 ms, 1.01x
ParStrategies ST Median3or5: OK (0.23s)
32.9 ms ± 1.5 ms, 1.00x
ParStrategies IO Median3or5: OK (0.23s)
33.0 ms ± 2.0 ms, 1.00x
Sequential ST AveragingMedian: OK (0.31s)
102 ms ± 7.6 ms, 3.08x
Threads IO Median3: OK (0.48s)
32.2 ms ± 982 μs, 0.98x
Threads IO Median3or5: OK (0.48s)
31.3 ms ± 1.6 ms, 0.95x
vector-algorithms heapsort: OK (0.31s)
103 ms ± 5.2 ms, 3.12x
fallback heapsort: OK (0.27s)
89.0 ms ± 4.7 ms, 2.70x
Sorting 10 random arrays of length 1,000,000 with many duplicates
C++: OK (1.03s)
339 ms ± 32 ms
Sequential ST Median3: OK (1.16s)
387 ms ± 5.5 ms, 1.14x
Sequential IO Median3: OK (0.99s)
329 ms ± 5.0 ms, 0.97x
ParStrategies ST Median3: OK (0.59s)
198 ms ± 15 ms, 0.58x
ParStrategies IO Median3: OK (0.60s)
198 ms ± 5.8 ms, 0.58x
Sequential ST Median3or5: OK (0.99s)
329 ms ± 8.3 ms, 0.97x
Sequential IO Median3or5: OK (1.00s)
331 ms ± 3.6 ms, 0.98x
ParStrategies ST Median3or5: OK (1.39s)
199 ms ± 5.0 ms, 0.59x
ParStrategies IO Median3or5: OK (0.60s)
199 ms ± 3.0 ms, 0.59x
Sequential ST AveragingMedian: OK (3.82s)
1.273 s ± 25 ms, 3.76x
Threads IO Median3: OK (0.88s)
294 ms ± 27 ms, 0.87x
Threads IO Median3or5: OK (1.92s)
274 ms ± 15 ms, 0.81x
vector-algorithms heapsort: OK (11.77s)
1.664 s ± 6.3 ms, 4.91x
fallback heapsort: OK (4.08s)
1.357 s ± 23 ms, 4.00x
Sorting 10 random arrays of length 10,000,000 with many duplicates
C++: OK (16.77s)
5.595 s ± 88 ms
Sequential ST Median3: OK (15.18s)
5.059 s ± 9.0 ms, 0.90x
Sequential IO Median3: OK (16.64s)
5.541 s ± 75 ms, 0.99x
ParStrategies ST Median3: OK (4.50s)
1.499 s ± 4.0 ms, 0.27x
ParStrategies IO Median3: OK (4.60s)
1.534 s ± 14 ms, 0.27x
Sequential ST Median3or5: OK (12.89s)
4.287 s ± 114 ms, 0.77x
Sequential IO Median3or5: OK (12.81s)
4.267 s ± 46 ms, 0.76x
ParStrategies ST Median3or5: OK (4.19s)
1.399 s ± 70 ms, 0.25x
ParStrategies IO Median3or5: OK (4.28s)
1.430 s ± 43 ms, 0.26x
Sequential ST AveragingMedian: OK (72.72s)
24.214 s ± 367 ms, 4.33x
Threads IO Median3: OK (10.38s)
3.450 s ± 125 ms, 0.62x
Threads IO Median3or5: OK (8.70s)
2.886 s ± 191 ms, 0.52x
vector-algorithms heapsort: OK (68.36s)
22.767 s ± 265 ms, 4.07x
fallback heapsort: OK (65.38s)
21.792 s ± 5.9 ms, 3.90x