# Questions tagged [sorting-network]

The tag has no usage guidance.

15 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)$ ...
716 views

380 views

### Would an optimal sorting network ever have to swap two numbers the “wrong” way

Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the ...
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 ...
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 ...
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 ...
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 ...
228 views

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