5 ms·
Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every
by proc0 7y ago
Interesting, but I'm surprised if this is the first time we have sorting algorithm that is swapping more than two elements at a time. I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested.
- Hendrikto 7y ago> I would have guessed every possible iteration of sorting algorithms has been already explored, proven and tested The search space is infinite, so exhaustively exploring it is impossible.
- foota 7y agoNit: it's possible that there is a finite number of Pareto optimal sorting algorithms, and it may be possible to enumerate those.
- dhash 7y agoOh man if I could efficiently enumerate algorithms across the Pareto front of anything I’d be a happy camper. Procedures that enumerate Turing machines are generally very easy, or nigh impossible
- foota 7y agoYou'd probably want to start by defining equivalence and then work from there. If your criteria for equivalence is loose enough you're already done, e.g., if you just look at runtime big O for randomized arrays or something you can't do better than n lg n so there's just the one Pareto optimal choice, with many possible implementations.
- eru 7y agoIt depends on your model of computation. O(n log n) is only the frontier for comparison based sorts that know nothing about the distribution of inputs. If your sorting algorithm is allowed to do anything else on your data, like hashing or looking at bits or arithmetic, different lower bounds might apply.
- jsnell 7y agoIt's a sorting network, invented in the 1950s.
- thaumaturgy 7y agoIt isn't. Sorting networks (https://en.wikipedia.org/wiki/Sorting_network https://en.wikipedia.org/wiki/Sorting_network) provide the best possible in-place sorting combinations for N elements, where N is currently < about 11. If somebody could find a way to generalize the sorting network algorithm for any number of input elements, they'd be settling the issue of sorting things pretty much forever. At lazy glance, it looks kind of like Quadsort has re-derived a variation of the 4-element sorting network.
- csense 7y ago> 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.
- thaumaturgy 7y agoI 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.
- csense 7y ago
- senderista 7y agoIf you think about it, the "quadswap" is just unrolled merge sort on 4 elements.
- kzrdude 7y agoGrailSort (GitHub) and related they swap blocks at a time, isn't that a precedent?