Smallest possible sorting network for given permutation

Question

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?

Answer 1

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.

Answer 2

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.