Skip to content

Comment on Quadsort: a stable non-recursive merge sortparent

Comments

The point I was trying to make is that sorting networks restrict your algorithm to a data-independent memory access pattern.

For some particular N, you might be able to find the smallest sorting network that sorts N elements. And then you might be able to find an even faster algorithm that sorts N elements using some strategy that's not equivalent to a sorting network (e.g., if your strategy does data-dependent memory access).

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.