Questions tagged [sorting-network]
The sorting-network tag has no usage guidance.
5
questions with no upvoted or accepted answers
15
votes
0answers
415 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 ...
5
votes
0answers
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 ...
4
votes
0answers
116 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 ...
1
vote
0answers
60 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 ...
1
vote
0answers
197 views
Algorithm for permuting elements using constant work space
I'm searching for an algorithm to do the following:
A 1->3
B 2->6
C 4->5
D 5->2
E 6->4
F 3->7
G 8->9
H 10->11
Elements A-H are stored on ...
