<p>The famous AKS sorting network allows one to sort <span class="math-container">$N$</span> elements via a circuit composed out of comparator gates, where the circuit has size <span class="math-container">$\mathcal{O}(n \log n)$</span> and depth <span class="math-container">$\mathcal{O}(\log n)$</span>.
The latest discussion of the hidden constants behind this construction that I could find were in the <a href="https://arxiv.org/pdf/1403.2777.pdf" rel="noreferrer">Zig-Zag sorting paper</a>, where (if I correctly understood) the author states that <span class="math-container">$13 613 047$</span> is the currently best known constant.</p>
<p><strong>Question:</strong>
Is this, as of 2020, still the best known hidden constant for a deterministic oblivious sorting algorithm with optimal complexity?</p>

CC BY-SA 4.0
2020-08-17T19:27:06.277Z
The Zig-Zag paper seems to say it isn’t $O(\log n)$ depth, so unfortunately I don’t think it applies as a solution to your question.
Geoffrey Irving
CC BY-SA 4.0
2020-08-18T15:52:34.857Z
Oh yes Zig-Zag has depth $\mathcal{O}(n)$. It was just the latest paper which discussed the hidden constants behind AKS as well. Since this is already over 5 years ago, I was wondering whether the hidden constants improved (for AKS).
Cryptonaut
<reference-request>
Best known hidden constant in complexity of AKS sorting networks
Cryptonaut
# Best known hidden constant in complexity of AKS sorting networks

(Asked by: username_0 on 2020-08-12)

The famous AKS sorting network allows one to sort $N$ elements via a circuit composed out of comparator gates, where the circuit has size $\mathcal{O}(n \log n)$ and depth $\mathcal{O}(\log n)$.
The latest discussion of the hidden constants behind this construction that I could find were in the [Zig-Zag sorting paper](https://arxiv.org/pdf/1403.2777.pdf), where (if I correctly understood) the author states that $13 613 047$ is the currently best known constant.

**Question:**
Is this, as of 2020, still the best known hidden constant for a deterministic oblivious sorting algorithm with optimal complexity?

**Tags:** reference-request
> **Comments:**
> **username_1**: The Zig-Zag paper seems to say it isn’t $O(\log n)$ depth, so unfortunately I don’t think it applies as a solution to your question.  
> **username_0**: Oh yes Zig-Zag has depth $\mathcal{O}(n)$. It was just the latest paper which discussed the hidden constants behind AKS as well. Since this is already over 5 years ago, I was wondering whether the hidden constants improved (for AKS).  

---

## 0 answers

