Quicksort revisited, Bubble sort fastest of all for small arrays, Quadsort

[dumblob]

As promised in daokoder/dao#307 (comment) , I'm copy-pasting the information here.

First of all, thanks for this initiative. It sounds valuable as sorting still seems an unoptimally solved issue in IT. I hope something measurable will come out of it.

2020 seems to have brought some new wind into the topic of sorting. There is e.g. Quadsort - a tight competitor to Grailsort.

But now it comes - a wisely implemented Bubble sort for small arrays is the fastest on ILP CPUs (i.e. all CPUs since 2000 including vast majority of embedded ones). When combined with Lomuto and Hoare partitioning schemes for Quick sort, we have a clear speed winner of "all time" - see Hoare’s Rebuttal and Bubble Sort’s Comeback and the corresponding repo https://github.com/gerben-s/quicksort-blog-post . It can also be made stable with some tweaks (and no additional memory), but there'll be slightly higher number of comparisons.

[Gaming32]

Scandum now also has a "Block Merge Sort" implementation based on Wiki Sort. It is called "Octosort," and its goal is to combine Quadsort with Wiki Sort for optimal performance.

[Gaming32]

This has been converted to a discussion for better discussion-y stuff