Interesting talk for the Julia sorting community

Offtopic
,
1

Here is an interesting talk given lately:

Giving details about TimSort and the new PowerSort and other interesting details.

This may be for @Lilith and other people who like things to be in proper order. Perhaps Julia can implement PowerSort (does it already?)

2

It is a nice improvement over timsort, but in general, Python and Julia have different sorting algorithms that will be faster. Python Lists are like Julia Vector{Any} which means the cost of swaps in Python is much cheaper than comparisons, while for most lists in Julia, the costs are reversed.

3

Perhaps the lesson to learn, is from Java, which has a different algorithm for primitive Vector{Int}-like vectors and Vector{big-struct} vectors. The relevant slide in the talk is:

dual-v-tim
dual-v-tim1920×1208 132 KB

It would be very Julian to have sort algorithm adapt to struct size, or some comparison cost hint.

4

AFAIU Julia already has a bunch of different sorting algorithms and chooses among them based on the element type, among other things.