Home...
Benchmarks von Sortieralgorithmen und Arraymustern
100 Mio. unsigned int64 (random 1...9223372036854775783) sortieren
https://de.wikipedia.org/wiki/Mergesort Erg=Sort(Array)
Hardware:  i9-7900X , 4.3 GHz, 32 GB RAM, Win10 
Software / Sprache Version/Code/Befehl Init + Load in s Sort in s Sum in s Threads
EXCEL\VBA QSort(aData): Do While x <= y ; jedoch long=i32 statt u64 (Rnd() * 2147483647) 6.641 235.219 241.860 1
EXCEL\VBA obj=System.Collections.ArrayList ...; obj.Add; .. Obj.Sort; jedoch long=i32 statt u64 246.670 122.250 368.920 1
Mathematica 12.0 Sort[NestList[Mod[6364136223846793005*#, 9223372036854775783] &, 13, nMax - 1]] 294.018 26.031 320.049 1
C# /MSVC2017 Array.Sort(myArray); Debug: AnyCPU 5.700 11.200 16.900 1
c++ /MSVC2017 std::sort(Arr.begin(),Arr.end(), std::less<myTyp>() ); 2.212 8.866 11.078 1
C# /MSVC2017 Array.Sort(myArray); Release: x64 4.500 8.540 13.040 1
c++ /MSVC2017 https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C 2.195 6.858 9.053 1
Julia 1.10.3 aA = Array{UInt64}(undef, n);Base.widemul…;aA.sort() 27.900 3.090 30.990 1
c++ /MSVC https://github.com/Voultapher/sort-research-rs/blob/main/src/cpp/thirdparty/intel_avx512/avx512-64bit-qsort.hpp 2.195 2.440 4.635 1
c++ /MSVC https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C + OMP 2.195 1.643 3.838 20
py + NumPy aV = np.empty(shape=(matrixNumber,), dtype=np.uint64); aV.sort() 31.900 1.062 32.962 1
c++ /MSVC BinaryRadix(unsigned long long *aA, int Len) 2.195 0.892 3.087 20
minGW\Boost Sort boost::sort::block_indirect_sort(v.begin(), v.end()) 0.460 20
rust+voracious_radix_sort numbers.voracious_mt_sort(available_parallelism().unwrap().get()); 2.402 0.254 2.656 20
rust+voracious_radix_sort MontgomeryInt::<u64>::new(13, &…; numbers.voracious_mt_sort(...); 0.522 0.254 0.776 20
           
Einfluss von Größe, Sortierverfahren und Arrayinhalt
      Arraygroesse=100000=100 Tsd. Arraygroesse=400000000=400 Mio. N=800 Mio. N=109=1 Mrd. 3*109=3 Mrd.
                                                                                               c++ c++
Algorithmus     Items  Type: UINT64      Dauer [s] Arrayinhalt Threads Algorithmus     Items       Dauer [s] Arrayinhalt Dauer [s] Dauer [s] Dauer [s]
 ---------   --------   ----   --------         ---------   --------   --------   ---------------- 
  crumsort  100000 64     0.002        rand() 2^47  1   crumsort  400000000 10.478       rand() 2^47  21.985 27.900
  quadsort  100000 64     0.002        rand() 2^47  1   quadsort  400000000 18.017       rand() 2^47  37.121 46.121
 mergesort  100000 64     0.002        rand() 2^47  20  mergesort  400000000 7.109       rand() 2^47  13.699 17.593
  fluxsort  100000 64     0.003        rand() 2^47  1   fluxsort  400000000 13.148       rand() 2^47  27.597 35.171
  blitsort  100000 64     0.004        rand() 2^47  1   blitsort  400000000 31.275       rand() 2^47 
BinaryRadix 100000 64     0.003        rand() 2^47  20 BinaryRadix 400000000 9.220       rand() 2^47  19.371 Shr56: 24.297
bester=crumsort mit     0.002 s                                                                                                                             bester=mergesort mit     7.109 s     Shr48: 24.213
20 Rust\voracious_mt_sort 1.400       rand() 2^47  2.724 3.384 12.980
20 MSVC2017\boost_sort 2.210       rand() 2^47  4.544 6.021 18.590
a[i] = mulModAsm64(a[i-1],6364136223846793005ULL,9223372036854775783ULL); if %2: a[i] >>= iGL % 27
  crumsort  100000 64     0.003  GL-Iterat >> mod27 1   crumsort  400000000 10.562 GL-Iterat >> mod27 21.611 27.062
  quadsort  100000 64     0.0035 GL-Iterat >> mod27 1   quadsort  400000000 17.876 GL-Iterat >> mod27 36.493 45.560
 mergesort  100000 64     0.002  GL-Iterat >> mod27 20  mergesort  400000000 7.068 GL-Iterat >> mod27 13.757 17.705
  fluxsort  100000 64     0.0035 GL-Iterat >> mod27 1   fluxsort  400000000 13.121 GL-Iterat >> mod27 28.171 35.671
  blitsort  100000 64     0.004  GL-Iterat >> mod27 1   blitsort  400000000 31.777 GL-Iterat >> mod27
BinaryRadix 100000 64     0.002  GL-Iterat >> mod27 20 BinaryRadix 400000000 5.987 GL-Iterat >> mod27 12.752 16.908
bester=mergesort mit     0.002 s                                                                                                          bester=BinaryRadix mit     5.987 s                     16.324
20 Rust\voracious_mt_sort 4.600 GL-Iterat >> mod27  18.036 32.917 362.105
20 minGW64\boost_sort 2.094 GL-Iterat >> mod27  4.415
20 MSVC2017\boost_sort 2.185 GL-Iterat >> mod27  4.566 5.726 18.738
                                                                                                        
  crumsort  100000 64     0.003  LehmerRandomU64 1   crumsort  400000000 10.519 LehmerRandomU64 21.392 27.016
  quadsort  100000 64     0.003  LehmerRandomU64 1   quadsort  400000000 18.026 LehmerRandomU64 36.622 45.466
 mergesort  100000 64     0.001  LehmerRandomU64 20  mergesort  400000000 7.087 LehmerRandomU64 13.824 17.342
  fluxsort  100000 64     0.003  LehmerRandomU64 1   fluxsort  400000000 13.156 LehmerRandomU64 27.747 35.193
  blitsort  100000 64     0.004  LehmerRandomU64 1   blitsort  400000000 31.493 LehmerRandomU64
BinaryRadix 100000 64     0.001  LehmerRandomU64 20 BinaryRadix 400000000 3.587 LehmerRandomU64 7.375 9.063
bester=BinaryRadix mit     0.001 s                                                                                                          bester=BinaryRadix mit     3.587 s                    
20 Rust\voracious_mt_sort 1.300 LehmerRandomU64  2.581 3.110 11.501
20 MSVC2017\boost_sort 2.172 LehmerRandomU64  4.551 5.833 18.635
                                                                                                        
  crumsort  100000 64     0.003        rand() 2^32  1   crumsort  400000000 5.265       rand() 2^32  14.069
  quadsort  100000 64     0.003        rand() 2^32  1   quadsort  400000000 15.722       rand() 2^32  40.769
 mergesort  100000 64     0.001        rand() 2^32  20  mergesort  400000000 7.133       rand() 2^32  17.626
  fluxsort  100000 64     0.003        rand() 2^32  1   fluxsort  400000000 7.303       rand() 2^32  19.211
  blitsort  100000 64     0.004        rand() 2^32  1   blitsort  400000000 24.378       rand() 2^32 
BinaryRadix 100000 64     0.002        rand() 2^32  20 BinaryRadix 400000000 8.468       rand() 2^32 
- 100000 64     -        rand() 2^32  1 CountingSort 400000000 1.550       rand() 2^32  3.132
bester=mergesort mit     0.001 s                                                                                                                              bester=CountingSort mit     1.550 s   
20 MSVC2017\boost_sort 1.707 rand() 2^32   3.564 4.488 14.533
                                                                                                        
  crumsort  100000 64     0.001       rand mod 100  1   crumsort  400000000 3.151      rand mod 100  7.869
  quadsort  100000 64     0.002       rand mod 100  1   quadsort  400000000 13.365      rand mod 100 
 mergesort  100000 64     0.001       rand mod 100  20  mergesort  400000000 7.061      rand mod 100 
  fluxsort  100000 64     0.001       rand mod 100  1   fluxsort  400000000 4.581      rand mod 100 
  blitsort  100000 64     0.002       rand mod 100  1   blitsort  400000000 16.046      rand mod 100 
BinaryRadix 100000 64     0.002       rand mod 100  20 BinaryRadix 400000000 8.071      rand mod 100 
- 100000 64     -       rand mod 100  1 CountingSort 400000000 0.887      rand mod 100  1.955
bester=crumsort mit     0.001 s                                                                                                                                 bester=CountingSort mit     0.887 s 
20 MSVC2017\boost_sort 1.396 rand()mod 100  2.923 3.723 11.568
                                                                                                        
  crumsort  100000 64     0.000    sum+=rand mod 5  1   crumsort  400000000     0.544    sum+=rand mod 5 
  quadsort  100000 64     0.000    sum+=rand mod 5  1   quadsort  400000000     0.933    sum+=rand mod 5 
 mergesort  100000 64     0.001    sum+=rand mod 5  20  mergesort  400000000 6.302   sum+=rand mod 5 
  fluxsort  100000 64     0.000    sum+=rand mod 5  1   fluxsort  400000000     0.565    sum+=rand mod 5 
  blitsort  100000 64     0.000    sum+=rand mod 5  1   blitsort  400000000     0.539    sum+=rand mod 5      1.353 
BinaryRadix 100000 64     0.002    sum+=rand mod 5  20 BinaryRadix 400000000 9.142   sum+=rand mod 5 
 CountingSort  100000 64     -    sum+=rand mod 5  1  CountingSort  400000000 4.078   sum+=rand mod 5 
bester=crumsort mit     0.000 s                                                                                                                                 bester=blitsort mit     0.539 s 
20 Rust\voracious_mt_sort 0.251   sum+=rand mod 5  0.497 0.614 1.861
20 MSVC2017\boost_sort 0.242   sum+=rand mod 5  0.479 0.595 1.814
                                                                                                        
  crumsort  100000 64     0.001          4er Saege  1   crumsort  400000000 5.140         4er Saege 
  quadsort  100000 64     0.001          4er Saege  1   quadsort  400000000 3.875         4er Saege 
 mergesort  100000 64     0.001          4er Saege  20  mergesort  400000000 6.714         4er Saege 
  fluxsort  100000 64     0.000          4er Saege  1   fluxsort  400000000 2.404         4er Saege 
  blitsort  100000 64     0.001          4er Saege  1   blitsort  400000000 5.056         4er Saege 
BinaryRadix 100000 64     0.002          4er Saege  20 BinaryRadix 400000000 7.592         4er Saege 
CountingSort 100000 64     -          4er Saege  1 CountingSort 400000000 1.241         4er Saege  2.378
bester=fluxsort mit     0.000 s                                                                                                                               bester=CountingSort mit     1.241 s   
                                                                                                        
  crumsort  100000 64     0.002          1 Dreieck  1   crumsort  400000000 20.280         1 Dreieck 
  quadsort  100000 64     0.001          1 Dreieck  1   quadsort  400000000 5.082         1 Dreieck 
 mergesort  100000 64     0.001          1 Dreieck  20  mergesort  400000000 6.366         1 Dreieck 
  fluxsort  100000 64     0.001          1 Dreieck  1   fluxsort  400000000 5.427         1 Dreieck 
  blitsort  100000 64     0.002          1 Dreieck  1   blitsort  400000000 20.257         1 Dreieck 
BinaryRadix 100000 64     0.002          1 Dreieck  20 BinaryRadix 400000000 7.585         1 Dreieck 
- 100000 64     -          1 Dreieck  1 CountingSort 400000000 1.213         1 Dreieck  2.396
bester=mergesort mit     0.001 s                                                                                                                                bester=CountingSort mit 1.213 s ; (bei 200 Mio. war flux vor quad!)
                                                                                                        
  crumsort  100000 64     0.000    sum-=rand mod 5  1   crumsort  400000000 4.112   sum-=rand mod 5 
  quadsort  100000 64     0.000    sum-=rand mod 5  1   quadsort  400000000 2.482   sum-=rand mod 5 
 mergesort  100000 64     0.001    sum-=rand mod 5  20  mergesort  400000000 6.176   sum-=rand mod 5 
  fluxsort  100000 64     0.000    sum-=rand mod 5  1   fluxsort  400000000 2.849   sum-=rand mod 5 
  blitsort  100000 64     0.000    sum-=rand mod 5  1   blitsort  400000000 4.102   sum-=rand mod 5 
BinaryRadix 100000 64     0.002    sum-=rand mod 5  20 BinaryRadix 400000000 8.632   sum-=rand mod 5 
bester=crumsort mit     0.000 s                                                                                                                            bester=quadsort mit     2.482 s      
20 MSVC2017\boost_sort 1.475   sum-=rand mod 5  2.647 4.264 9.567
                                                                                                        
  crumsort  100000 64     0.003   4 fallende Saege  1   crumsort  400000000 37.351  4 fallende Saege 
  quadsort  100000 64     0.002   4 fallende Saege  1   quadsort  400000000 8.630  4 fallende Saege 
 mergesort  100000 64     0.001   4 fallende Saege  20  mergesort  400000000 6.760  4 fallende Saege 
  fluxsort  100000 64     0.003   4 fallende Saege  1   fluxsort  400000000 9.091  4 fallende Saege 
  blitsort  100000 64     0.004   4 fallende Saege  1   blitsort  400000000 37.341  4 fallende Saege 
BinaryRadix 100000 64     0.002   4 fallende Saege  20 BinaryRadix 400000000 7.615  4 fallende Saege 
- 100000 64     -   4 fallende Saege  1 CountingSort 400000000 1.299  4 fallende Saege  2.346
bester=mergesort mit     0.001 s                                                                                                                            bester=CountingSort mit     1.299 s    
                                                                                                        
  crumsort  100000 64     0.001      1/4rauf +rand  1   crumsort  400000000 5.052     1/4rauf +rand 
  quadsort  100000 64     0.001      1/4rauf +rand  1   quadsort  400000000 5.528     1/4rauf +rand 
 mergesort  100000 64     0.001      1/4rauf +rand  20  mergesort  400000000 6.590     1/4rauf +rand 
  fluxsort  100000 64     0.001      1/4rauf +rand  1   fluxsort  400000000 3.534     1/4rauf +rand 
  blitsort  100000 64     0.001      1/4rauf +rand  1   blitsort  400000000 8.786     1/4rauf +rand 
BinaryRadix 100000 64     0.003      1/4rauf +rand  20 BinaryRadix 400000000 7.791     1/4rauf +rand 
- 100000 64     -      1/4rauf +rand  1 CountingSort 400000000 1.114     1/4rauf +rand  2.342
bester=mergesort mit     0.001 s                                                                                                                               bester=CountingSort mit     1.114 s  
                                                                                                        
  crumsort  100000 64     0.002      1/2rauf +rand  1   crumsort  400000000 5.236     1/2rauf +rand 
  quadsort  100000 64     0.002      1/2rauf +rand  1   quadsort  400000000 9.161     1/2rauf +rand 
 mergesort  100000 64     0.001      1/2rauf +rand  20  mergesort  400000000 6.793     1/2rauf +rand 
  fluxsort  100000 64     0.002      1/2rauf +rand  1   fluxsort  400000000 4.953     1/2rauf +rand 
  blitsort  100000 64     0.002      1/2rauf +rand  1   blitsort  400000000 13.805     1/2rauf +rand 
BinaryRadix 100000 64     0.002      1/2rauf +rand  20 BinaryRadix 400000000 8.007     1/2rauf +rand 
- 100000 64     -      1/2rauf +rand  20 CountingSort 400000000 1.092     1/2rauf +rand  2.191
bester=mergesort mit     0.001 s                                                                                                                        bester=CountingSort mit     1.092 s         
16777216 33554433 16777218 33554435 16777220 33554437 16777222 33554439 16777216 33554433 16777218 33554435 16777220 33554437 16777222 33554439
  crumsort  100000 64     0.003    ascending tiles  1   crumsort  400000000 10.627   ascending tiles 
  quadsort  100000 64     0.001    ascending tiles  1   quadsort  400000000 9.440   ascending tiles 
 mergesort  100000 64     0.001    ascending tiles  20  mergesort  400000000 6.478   ascending tiles 
  fluxsort  100000 64     0.001    ascending tiles  1   fluxsort  400000000 10.358   ascending tiles 
  blitsort  100000 64     0.003    ascending tiles  1   blitsort  400000000 23.741   ascending tiles 
BinaryRadix 100000 64     0.003    ascending tiles  20 BinaryRadix 400000000 27.152   ascending tiles 
 -  100000 64     -    ascending tiles  1  CountingSort  400000000 1.822   ascending tiles  3.297
bester=mergesort mit     0.001 s                                                                                                                                bester=CountingSort mit     1.822 s
20 MSVC2017\boost_sort 1.223   ascending tiles  2.524 3.075 9.443
0 1073741824 536870912 1610612736 268435456 1342177280 805306368 1879048192 0 1073741824 536870912 1610612736 268435456 1342177280 805306368 1879048192
  crumsort  100000 64     0.003       bit reversal  1   crumsort  400000000 10.537      bit reversal 
  quadsort  100000 64     0.003       bit reversal  1   quadsort  400000000 18.637      bit reversal 
 mergesort  100000 64     0.001       bit reversal  20  mergesort  400000000 7.134      bit reversal 
  fluxsort  100000 64     0.003       bit reversal  1   fluxsort  400000000 12.987      bit reversal 
  blitsort  100000 64     0.004       bit reversal  1   blitsort  400000000 31.405      bit reversal 
BinaryRadix 100000 64     0.002       bit reversal  20 BinaryRadix 400000000 8.035      bit reversal 
bester=mergesort mit     0.001 s                                                                                                                               bester=mergesort mit     7.134 s 
20 MSVC2017\boost_sort 2.226   bit reversal   4.589 5.845 18.064
16777216 3611686018427387901 16777218 3611686018427387895 16777220 3611686018427387889 16777222 3611686018427387883 16777224 3611686018427387877
  crumsort  100000 64     0.003       mod2?add1:sub3  1   crumsort  400000000 10.464      mod2?add1:sub3  21.658
  quadsort  100000 64     0.001       mod2?add1:sub3  1   quadsort  400000000 9.336      mod2?add1:sub3  20.098
 mergesort  100000 64     0.001       mod2?add1:sub3  20  mergesort  400000000 6.538      mod2?add1:sub3  13.255
  fluxsort  100000 64     0.001       mod2?add1:sub3  1   fluxsort  400000000 2.584      mod2?add1:sub3  11.202 12.528
  blitsort  100000 64     0.003       mod2?add1:sub3  1   blitsort  400000000 26.582      mod2?add1:sub3 
BinaryRadix 100000 64     0.001       mod2?add1:sub3  20 BinaryRadix 400000000 13.864      mod2?add1:sub3  27.448
bester=fluxsort mit     0.001 s                                                                                                                               bester=fluxsort mit     2.584 s 
20 Rust\voracious_mt_sort 1.540       mod2?add1:sub3  2.890 3.668 12.194
20 MSVC2017\boost_sort 1.686       mod2?add1:sub3  3.444 4.798 13.264
mergesort  https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#C iterativ + OMP
BinaryRadix https://cboard.cprogramming.com/c-programming/178915-binary-radix-sort.html
flux..crum.. https://github.com/scandum
LehmerRandomU64 https://en.wikipedia.org/wiki/Lehmer_random_number_generator#Sample_C99_code int128 -> MASM
Rust funnylurch: https://matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=265477&start=0#p1932664
Animation: https://homepages.bluffton.edu/~nesterd/apps/SortingDemo.html
boost Sort: https://www.boost.org/doc/libs/1_85_0/libs/sort/doc/html/sort/parallel.html#sort.parallel.block_indirect_sort
CountingSort: https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort#C wegen RAM-Bedarf nur (max-min) < 2^32

weitere Benchmarks:
Benchmark NextPrime
Benchmark 3^n
Benchmark LinearSolver
Liste mathematische Rekorde (viele Nachkommastellen)