# Questions tagged [sorting-network]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
331 views

### Probability that a random sorting network works

Given $n$ inputs $x_0, \ldots, x_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x_i, x_j$ with $i < j$ and adding a comparator gate that swaps ...
234 views

### Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

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 ...
349 views

### Is it possible to find the median with a linear size sorting network?

Is there a sorting network that makes only $O(n)$ comparisons and finds the median? The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
887 views

### Is the bitonic sort algorithm stable?

I was wondering, is the bitonic sort algorithm stable? I searched the original paper, wikipedia and some tutorials, could not find it. It seems to me that it should be, as it is composed of merge / ...
124 views

### Boolean circuit for efficient array indexing

Suppose that I have an array $\{a_i\}$ of $n$ elements, each $k$ bits wide, and an array $\{b_i\}$ of $n$ elements, each $\lceil\log_2n\rceil\le k$ bits wide. I need a boolean circuit which will ...
202 views

### Does the 0-1 principle apply to merge networks?

For sorting networks, the 0-1 principle says that if it can sort any sequence of 0's and 1's, then it can sort any list. What if I want to build a comparison-swap network for merging two pre-sorted ...
616 views

328 views

### Parallel sorting: introduction and state of research

there seem to exist papers on parallel sorting, but I have not found a good introduction into this topic. So, do you know a good summary or introduction into parallel sorting algorithms? In ...
### 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)$ ...
### Selection algorithm on depth-$\text{O}(\log n)$ sorting network
Is there a sorting network of depth $\text{O}(\log n)$ for selecting the $i$th order statistic? Remark: I've already asked a related question in a different context. Although the two questions are ...