# Smallest possible sorting network for given permutation

I need to build a sorting (comparator) network using comparators for a specific permutation on a set $$x_1, \dots, x_n$$. The solution should not be a general sorting network that sorts every permutation. I should build the smallest possible sorting network for the given permutation (the depth of the network should be $$O(\log n)$$).

I am really unsure about how to approach this problem. I thought I might go through the permutation and if the number is in the correct spot then leave it, if not then place a comparator with this number as input and the number that should be here as the second input. But I don't think that the depth of such network would be $$O(\log n)$$. So how would I go about building the needed network?

• There’s a general purpose sorting network of logarithmic depth, the AKS sorting network. – Yuval Filmus Dec 8 '18 at 16:28
• @YuvalFilmus: As I have stated the solution should not be a general sorting network that sorts every permutation. – ThePopa611 Dec 8 '18 at 16:53
• @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. – Yuval Filmus Dec 9 '18 at 7:54

For concreteness, let us assume that $$x_1,\ldots,x_n$$ are numbers between $$1$$ and $$n$$, and that a comparison puts the smaller number at the smaller index.

Consider first the case in which $$n$$ is even. We divide $$x_1,\ldots,x_n$$ into two halves: $$x_1,\ldots,x_{n/2}$$ and $$x_{n/2+1},\ldots,x_n$$. Let us call a number misplaced if it is in the wrong half: that is, a number in the first half is misplaced if it is in $$\{n/2+1,\ldots,n\}$$, and a number in the second half is misplaced if it is in $$\{1,\ldots,n/2\}$$. Note that the first half contains as many misplaced numbers as the second half (why?). Using one round of parallel comparisons, you can exchange the locations of the misplaced numbers, and guarantee that $$\{x_1,\ldots,x_{n/2}\} = \{1,\ldots,n/2\}$$, and similarly $$\{x_{n/2+1},\ldots,x_n\} = \{n/2+1,\ldots,n\}$$. Now recursively sort each half, in parallel.

When $$n>1$$ is odd, we use the same strategy, dividing the array into two unequal halves, say the first half larger than the second by one element.

As an illustration, suppose that we are given the array $$3,4,2,6,1,5$$ We switch $$1$$ and $$4$$ to obtain $$3,1,2,6,4,5$$ Now we recursively sort $$3,1,2$$ and $$6,4,5$$.

In order to sort $$3,1,2$$, we first exchange $$1$$ and $$3$$ to obtain $$1,3,2$$, and then sort the two halves $$1$$ and $$3,2$$ in parallel, which means to exchange $$2$$ and $$3$$.

Sorting $$6,4,5$$ is completely analogous.

• Also one more additional question: does that mean that the number of comparators will be $O(n)$? – ThePopa611 Dec 9 '18 at 12:43
• This construction only guarantees $O(n\log n)$. – Yuval Filmus Dec 9 '18 at 17:20

Well instead, here is a testing of a logic for a "sorting network" as columns left-to-right:

3 2 2 2 1

2 3 3 1 2

4 4 1 3 3

1 1 4 4 4

or

3 2 2 1

2 3 1 2

4 1 3 3

1 4 4 4

or

3 3 2 2 1

2 2 3 1 2

4 1 1 3 3

1 4 4 4 4

and

3 3 2 2 2 1 1

5 2 3 3 1 2 2

2 5 5 1 3 3 3

1 1 1 5 5 5 4

4 4 4 4 4 4 5

or

3 3 2 2 1

5 2 3 1 2

2 5 1 3 3

1 1 5 4 4

4 4 4 5 5

or

3 3 2 2 1

5 2 3 1 2

2 1 1 3 3

1 4 4 4 4

4 5 5 5 5

The idea being that the intermediate sorts must have purpose. So this edited post, and suggestion of a structure, is now more like a question because it says "or" between sets of examples.

• (1) This isn’t a sorting network; (2) You forgot about the logarithmic depth constraint. – Yuval Filmus Dec 9 '18 at 7:50