<p>there is some research angle here dating at least to Knuth's Art of Computer Programming and presumably earlier in finding <em>optimal</em> sorting networks for low $n$. its intractable to find optimal sorting networks for small $n$ but it has been done up to about $n=10$ eg as in this recent notable paper, also using SAT. details about how to reduce the problem to SAT are in the paper. basically a large SAT formula encoding is built that asserts "these boolean variables configure a circuit that sorts all inputs for size $n$". (the more nonresearch angle is to use <a href="http://en.wikipedia.org/wiki/Sorting_algorithm" rel="nofollow">existing sort algorithms</a> or sorting network configurations as mentioned in the paper by Har-Peled you cite to generate the <em>(nonoptimal)</em> circuits, this is more like a CS/EE exercise.)</p>

<p><a href="http://arxiv.org/abs/1310.6271" rel="nofollow">Optimal Sorting Networks</a> Daniel Bundala, Jakub Závodný</p>

<blockquote>
  <p>This paper settles the optimality of sorting networks given in The Art of Computer Programming vol. 3 more than 40 years ago. The book lists efficient sorting networks with n &lt;= 16 inputs. In this paper we give general combinatorial arguments showing that if a sorting network with a given depth exists then there exists one with a special form. We then construct propositional formulas whose satisfiability is necessary for the existence of such a network. Using a SAT solver we conclude that the listed networks have optimal depth. For n &lt;= 10 inputs where optimality was known previously, our algorithm is four orders of magnitude faster than those in prior work.</p>
</blockquote>

CC BY-SA 3.0
2014-04-02T01:47:55.797Z
Why the downvote?!
Mau
CC BY-SA 3.0
2014-04-01T16:43:56.000Z
2014-04-01T16:43:56.000Z
vzn
<p>How can I construct a <a href="http://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">sorting network</a> for $k$ numbers?</p>

<p>My goal is to implement sorting networks in Java for $k$ in the range $[3,\hspace{-0.03 in}32]$.
<br>
To be even more specific, I only want to sort integers.</p>

<p>I found some implementation in this <a href="http://www.drdobbs.com/sorting-networks/184402663" rel="nofollow noreferrer">article</a> (pages 2-3), but I don't understand it.</p>

<p>I been trying to convert this problem to SAT. I started with a simple non-optimal network: $[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01]$ (<a href="https://cs.stackexchange.com/a/23261/10572">source</a>). The idea is to convert it to SAT, find the shortest equal-satisfiable SAT formula, and convert it back to a network representation. The problem is that in the network, the order of comparisons is important, so I don't know hot to convert it to SAT. It sounds like some one has already been trying to do something like <a href="http://courses.engr.illinois.edu/cs573/fa2012/lec/lec/19_sortnet.pdf" rel="nofollow noreferrer">this</a>, but I don't understand it completely. </p>

<p><a href="https://cs.stackexchange.com/questions/23251/find-the-minimum-amount-of-swaps-to-sort-array">Related question.</a></p>

<sorting>
How can I construct sorting network for $k$ numbers
Ilya Gazman
# How can I construct sorting network for $k$ numbers

(Asked by: username_0 on 2014-04-01)

How can I construct a [sorting network](http://en.wikipedia.org/wiki/Sorting_network) for $k$ numbers?

My goal is to implement sorting networks in Java for $k$ in the range $[3,\hspace{-0.03 in}32]$.
  
To be even more specific, I only want to sort integers.

I found some implementation in this [article](http://www.drdobbs.com/sorting-networks/184402663) (pages 2-3), but I don't understand it.

I been trying to convert this problem to SAT. I started with a simple non-optimal network: $[01, 12, \ldots, (n-1)n, 01, 12, \ldots, (n-2)(n-1), \ldots, 01, 12, 01]$ ([source](https://cs.stackexchange.com/a/23261/10572)). The idea is to convert it to SAT, find the shortest equal-satisfiable SAT formula, and convert it back to a network representation. The problem is that in the network, the order of comparisons is important, so I don't know hot to convert it to SAT. It sounds like some one has already been trying to do something like [this](http://courses.engr.illinois.edu/cs573/fa2012/lec/lec/19_sortnet.pdf), but I don't understand it completely.

[Related question.](https://cs.stackexchange.com/questions/23251/find-the-minimum-amount-of-swaps-to-sort-array)

**Tags:** sorting

---

## 1 answers

### Answer by username_1 on 2014-04-01. Score: 3 | Accepted answer

there is some research angle here dating at least to Knuth's Art of Computer Programming and presumably earlier in finding *optimal* sorting networks for low $n$. its intractable to find optimal sorting networks for small $n$ but it has been done up to about $n=10$ eg as in this recent notable paper, also using SAT. details about how to reduce the problem to SAT are in the paper. basically a large SAT formula encoding is built that asserts "these boolean variables configure a circuit that sorts all inputs for size $n$". (the more nonresearch angle is to use [existing sort algorithms](http://en.wikipedia.org/wiki/Sorting_algorithm) or sorting network configurations as mentioned in the paper by Har-Peled you cite to generate the *(nonoptimal)* circuits, this is more like a CS/EE exercise.)

[Optimal Sorting Networks](http://arxiv.org/abs/1310.6271) Daniel Bundala, Jakub Závodný

> This paper settles the optimality of sorting networks given in The Art of Computer Programming vol. 3 more than 40 years ago. The book lists efficient sorting networks with n <= 16 inputs. In this paper we give general combinatorial arguments showing that if a sorting network with a given depth exists then there exists one with a special form. We then construct propositional formulas whose satisfiability is necessary for the existence of such a network. Using a SAT solver we conclude that the listed networks have optimal depth. For n <= 10 inputs where optimality was known previously, our algorithm is four orders of magnitude faster than those in prior work.

> **Comments:**
> **username_2**: Why the downvote?!  

---

