I want to permute a vector using comparison networks. This is the only method I have at my disposal.
My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector at the start of the network and instead of comparing the quantities I draw a random bit. this bit determines whether I perform the exchange or not.
My intuition tells me, that I would not need a full sorting network for that matter. So I was wondering if there is ANY COMPARISON network with complexity similar or smaller than nlog(n) that I could use instead or those sorting networks would allow me to obtain all the set of permutations of a vector.
thanks so much in advance