potential implementation list

[matu3ba]

Optimization parameters:

1. necessary memory, 2. stability, 3. variance of performance, 4. performance

• pdqSort #7
• timsort
• https://lib.rs/crates/dmsort ? not sure, if there is a better one fort mostly sorted data
• probably more niche, since cache is king: https://github.com/scandum/quadsort
• cheating (3k? LOC SIMD abstraction per architecture): SIMD accelerated quicksort etc.
• Discussion scandum/crumsort#1 not yet, as it has several yet unfixed downsides

[matu3ba]

scandum wrote another sorting algorithm with a nice overview table: scandum/crumsort#1

You might want to take a lookt at the bottom tables: fluxsort and crumsort outperform pdqsort in all cases.
However, timsort is not compared.

APPENDUM: What I dislike most is that there are not "trivially copypastable instructions/scripts" to compare the algorithms and author does not provide spec of used machine.

UPDATE: Author fixed all issues after being contacted.

[alichraghi]

yeah, i seen it, thanks for mentioning here. exams has completely filled my time for up to two months. there's a lot of programming things to do in the summer.

[matu3ba]

lithdrew dropped a comment of google getting 1GB/s with SIMD-accelerated quicksort https://opensource.googleblog.com/2022/06/Vectorized%20and%20performance%20portable%20Quicksort.html

However, this depends on https://github.com/google/highway to unify common SIMD routines across platforms.

UPDATE 20240418: There is a company repo claiming to port some stuff from google highway.