3 ms·
Faster than quicksort?
by EGreg 4y ago
Faster than quicksort?
- hajile 4y agoBeating quicksort alone is almost always as easy as swapping insertion sort once you get down to around 14 elements. This is used by C#'s quicksort (which also swaps to heapsort after a depth of 32 IIRC) and also in Timsort in JS, Java, Python, etc.
- repiret 4y agoQuicksort isn’t stable.
- orlp 4y agoSchoolbook exchange quicksort isn't stable, but quicksort absolutely can be implemented stably, which I do in glidesort: https://www.youtube.com/watch?v=2y3IK1l6PI4 https://www.youtube.com/watch?v=2y3IK1l6PI4.
- janwas 4y agoFurther to that, many use cases of Quicksort have unique keys, so stable is the same as unstable. Example: ascending indices appended to the key, when sorting large records where we don't want to move around the entire record.
- scandum 4y agoBlitsort is a hybrid quicksort, see title. It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort https://github.com/scandum/crumsort