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

> If somebody could find a way to generalize the sorting network algorithm for any number of input elements

In section 2 in that Wikipedia article, it links to many constructions that do exactly that.

A couple are O(n log(n)), but complicated and impractical. The algorithms people use are O(n log^2(n)) ones.

FWIW, sorting networks are data-independent. I.e. for any input, you always compare-and-swap the same elements.






I was imprecise. I was talking about the construction of optimal sorting networks. You're correct to point out that there are several approaches now for constructing sorting networks for arbitrary numbers of inputs, but as noted in that section, they all have some very important tradeoffs. I said, "...provide the best possible in-place sorting combinations for N elements, where N is currently < about 11"; the 11 there was a reference to this part from the second section of that article:

"For one to eleven inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉. The first ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases n = 9 and n = 10 took until 2014 to be resolved.[11] An optimal network for size 11 was found in December of 2019 by Jannis Harder..."

Clearly I also should've said < ~12.




Applications are open for YC Summer 2020

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

Search: