# Questions tagged [sorting-network]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
54 views

### Practical Data-oblivious Compaction?

Compaction is a particularly weak form of sorting. The problem can be phrased as follows: Given an array $A$ of $N$ cells, with at most $R$ of the cells distinguished (say by a bit), produce an array ...
98 views

### Is there any efficient Network stable sort (not bubble sort)?

Ok, I realize Bitonic sort is not stable and any attempt to make it stable is inefficient, or is there some efficient way? But is there some other network sort which is indeed stable beside bubble ...
371 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 ...
253 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 ...
393 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 ...
1k 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 / ...
128 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 ...
215 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 ...
679 views

330 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 ...