# Questions tagged [sorting-network]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
2k views

### Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times? As far as I know, the only way to sort with $O(\log n)$ ...
720 views

Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)... 1answer 689 views ### Probability of generating a desired permutation by random swaps I'm interested in the following problem. We're given as input a "target permutation"$\sigma\in S_n$, as well as an ordered list of indices$i_1,\ldots,i_m\in [n-1]$. Then, starting with the list$L=...
The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...