[prirun]

"We find that for smaller n≲ 262144, JesseSort is slower than Python’s default sort."

[repsilat]

I wonder about the global statistics of sorted data... Is the most common number of elements to sort zero? Certainly less than ten?

What about the median? Two elements to sort? One? Zero again?

[lblume]

The question is also for which list lengths the performance matters most. When sorting a few strings (<20), whether the algorithm uses 5 or 7 comparisons would usually not matter too much. So to find the optimal algorithm for a given situation, we would have to compute a weighted average by list length importance on the performances of the algorithm per list length.

[3eb7988a1663]

Don't high performance systems have heuristics to decide what specific algorithms to use at runtime? It is not unimaginable to think that there could be a function dedicated to small vs large collections.

Assuming the results hold, someone has to decide if the additional complexity is worth the performance. For something like BLAS, go nuts. For Python standard library, maybe not.