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?