Hacker News new | past | comments | ask | show | jobs | submit login

I've never seen a sorting algorithm that uses a non-binary comparison function to order values. Is that a novel technique?

It seems really obvious in hindsight, so I'm sure there's just prior art I don't know about.






This is still binary comparison.

There are, in general, a number of different sorting algorithms which are optimized for a specific number of elements. In this case, four. It uses five binary comparisons to sort four elements.

You can find other algorithms like this, such as an algorithm that uses seven comparisons to sort five items, or one that uses ten comparisons to sort six items.


Ah, I completely misunderstood what was going on with the quad swap at the start. Rereading it makes more sense. Thanks!

If tried that in eg Haskell to see if I can beat the standard library's highly optimized sort.

In theory, you can get O(n log k) performance, where k is the number of distinct elements (so k <= n). And crucially: you don't need to know k up-front.

In practice, all my attempts were absolutely slower than the standard approach based on binary comparisons only. (But that's saying more about me than about the domain.)


Perl and C++ use the <=> "spaceship" operator for that. Cmp for strings in Perl.



Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: