search

orlp / glidesort

A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
1.57k stars 24 forks source link

Implement optimizations from Stavenga's article #9

Closed safinaskar closed 1 year ago

safinaskar commented 1 year ago

Please, use optimizations from this cool @gerben-stavenga's article: https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html

orlp commented 1 year ago

I am aware of Gerben's work, and there is a lot of similar optimizations in glidesort. Is there any optimization in particular that you think is missing?

safinaskar commented 1 year ago

Okay. You do insertion sort for small arrays ( https://github.com/orlp/glidesort/blob/5e263ae/src/small_sort.rs#L417 ) instead of suggested bubble sort

orlp commented 1 year ago

I do block insertion sort. In my tests it was faster than bubblesort. The devil is always in the details though.

safinaskar commented 1 year ago

Okay

gerben-stavenga commented 1 year ago

I do block insertion sort. In my tests it was faster than bubblesort. The devil is always in the details though.

Just a drive by comment as I was tagged. The devil is indeed in the details, the article is focussed on sorting rather primitive types (small size <16 bytes) on primitive values. In particular the code works best when sorting array of pointers (primitive types) to structures on some integer/float member, which covers a lot of useful actual sorting tasks.

But what I'm suggesting is NOT just bubble sort but what I call bubble2 sort and it's crucial to use a compiler that is good enough to actually compile the code to branchless instructions (llvm). I'm fairly sure that when you test properly you'd see that in that case it's likely better then insertion sort/block insertion sort. Although that also depends on the size range one uses for the small sort cutoff. Insertion sort will start beating it at large enough size, but below 32 it's likely bubble2.