4 ms·
This is well known (google trivial sorting network!), and it would never be published anywhere peer-reviewed. Good reminder that Arxiv is not peer-reviewed :/
by javierlc 2y ago
This is well known (google trivial sorting network!), and it would never be published anywhere peer-reviewed.
Good reminder that Arxiv is not peer-reviewed :/
- justinpombrio 2y agoI did search for "trivial sorting network", but the only networks that were called trivial were the ones for exactly two elements, while this algorithm sorts an arbitrary number of elements. Could you link to what you're talking about? And what's its big-O runtime?
- javierlc 2y agoThere is discussion about Sorting Networks in the old post (find link in one of the top comments of this post)
- javierlc 2y agoThis is a much stronger result from the 80s: https://www.researchgate.net/publication/221590321_An_On_log_n_Sorting_Network https://www.researchgate.net/publication/221590321_An_On_log...
- deleted 2y ago[deleted]