Timeline for Smallest possible sorting network for given permutation
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2018 at 12:40 | vote | accept | Popa611 | ||
| Dec 9, 2018 at 7:54 | comment | added | Yuval Filmus | @D.W. Sorting networks, also known as comparator circuits, are a general model of computation, defined in textbooks such as CLRS. A sorting network is just a type of circuit - it doesn’t have specific semantics. In this case, we don’t need it to sort all possible inputs, but just one input permutation; and we want it done in logarithmic depth. As I commented above, you can just use the AKS sorting network, but the intended solution was probably the divide-and-conquer approach outlined in my answer. | |
| Dec 9, 2018 at 2:57 | answer | added | S Spring | timeline score: 0 | |
| Dec 9, 2018 at 1:39 | answer | added | Yuval Filmus | timeline score: 1 | |
| Dec 9, 2018 at 1:31 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 1 character in body
|
| Dec 9, 2018 at 1:18 | history | edited | Yuval Filmus | CC BY-SA 4.0 |
added 3 characters in body
|
| Dec 8, 2018 at 16:53 | comment | added | Popa611 | @YuvalFilmus: As I have stated the solution should not be a general sorting network that sorts every permutation. | |
| Dec 8, 2018 at 16:28 | comment | added | Yuval Filmus | There’s a general purpose sorting network of logarithmic depth, the AKS sorting network. | |
| Dec 8, 2018 at 15:20 | history | asked | Popa611 | CC BY-SA 4.0 |