************************************************************ ** ** ** B O O S T S O R T ** ** ** ** O B J E C T S B E N C H M A R K ** ** ** ************************************************************ ============================================================= = OBJECT COMPARISON = = --------------------- = = = = The objects are arrays of 64 bits numbers = = They are compared in two ways : = = (H) Heavy : The comparison is the sum of all the numbers = = of the array = = (L) Light : The comparison is with the first element of = = the array, as a key = = = ============================================================ ************************************************************ ** ** 1562500 OBJECTS UINT64_T [128] ** ** ************************************************************ [ 1 ] std::sort [ 2 ] pdqsort [ 3 ] std::stable_sort [ 4 ] spinsort [ 5 ] flat_stable_sort [ 6 ] spreadsort [ 7 ] timsort [ 8 ] skasort [ 9 ] timsort with swapping optimization | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | [ 7 ] | [ 8 ] | [ 9 ] | | H L | H L | H L | H L | H L | H L | H L | H L | H L | --------------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+ random |10.26 4.06| 5.33 1.72| 9.92 7.41| 7.19 4.18| 6.00 3.55| 4.13 0.99| 8.23 5.68| 3.13 1.86| 4.85 0.97| | | | | | | | | | | sorted |10.12 2.56| 1.02 0.04| 7.87 6.32| 0.36 0.02| 0.38 0.02| 0.36 0.02| 0.36 0.02| 2.43 1.50| 0.38 0.03| sorted + 0.1% end |11.44 2.59| 1.75 0.07| 7.81 6.27| 1.84 1.11| 0.46 0.03| 3.15 0.44| 0.40 0.02| 2.47 1.51| 0.43 0.04| sorted + 1% end |11.22 2.67| 1.63 0.07| 7.98 6.50| 1.93 1.14| 0.47 0.04| 3.01 0.44| 0.41 0.03| 2.49 1.51| 0.45 0.04| sorted + 10% end |11.50 3.07| 1.29 0.06| 8.60 6.87| 2.52 1.46| 0.57 0.11| 3.21 0.46| 0.57 0.08| 2.72 1.68| 0.52 0.09| | | | | | | | | | | sorted + 0.1% mid |14.44 4.74| 4.61 0.03| 8.43 6.24| 5.05 0.02| 1.52 0.02| 4.11 0.02| 0.81 0.02| 2.51 0.75| 0.58 0.03| sorted + 1% mid |12.62 5.02| 4.62 0.03| 8.65 6.44| 5.19 0.02| 2.24 0.02| 3.92 0.02| 1.02 0.02| 2.62 0.79| 0.69 0.03| sorted + 10% mid |10.92 5.24| 4.70 0.03| 9.46 6.81| 5.74 0.02| 2.58 0.02| 3.90 0.02| 2.26 0.02| 3.30 0.83| 1.40 0.03| | | | | | | | | | | reverse sorted | 8.41 3.00| 1.14 0.34| 8.43 6.63| 2.79 1.89| 1.96 1.22| 4.48 0.86| 1.89 1.24| 2.75 1.76| 0.87 0.53| rv sorted + 0.1% end|14.85 4.66| 4.16 0.69| 8.26 6.70| 2.84 1.94| 1.59 0.97| 4.16 0.84| 1.60 1.23| 2.73 1.77| 0.91 0.53| rv sorted + 1% end|12.01 3.80| 4.16 0.66| 8.33 6.62| 2.92 1.91| 1.59 0.96| 4.11 0.84| 1.63 1.23| 2.79 1.80| 0.93 0.53| rv sorted + 10% end|11.01 3.79| 4.20 0.77| 8.98 7.21| 3.41 2.21| 1.90 1.04| 4.24 0.86| 1.80 1.23| 3.06 1.95| 1.00 0.58| | | | | | | | | | | rv sorted + 0.1% mid|14.56 4.91| 1.99 0.03| 8.69 6.43| 7.22 0.02| 2.45 0.02| 4.30 0.02| 4.00 0.02| 2.79 0.76| 0.95 0.03| rv sorted + 1% mid|12.89 5.30| 1.98 0.03| 8.86 6.75| 7.31 0.02| 4.44 0.02| 4.48 0.02| 5.31 0.02| 3.37 0.78| 1.22 0.03| rv sorted + 10% mid|11.82 5.37| 2.43 0.03|11.25 7.10| 8.25 0.02| 4.85 0.02| 4.36 0.02| 6.32 0.02| 3.38 0.83| 2.12 0.03| --------------------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+-----------+