When Ajtai, Komlos and Szemeredi described the AKS Sorting Network in 1983, resulting in an O(n
log n) sorting circuit, few could have imagined that there would be little to no further understanding
and advancements in this field for almost 40 years. It seems like n log n might possibly be a speed-of-light barrier for sorting circuits.

But in her talk at Upgrade 2020, the recent NTT Research Summit, Dr. Elaine Shi describes how to construct sorting circuits that overcome the n log n barrier for short keys.

Shi, a professor at Carnegie Mellon University (on leave from Cornell), describes results over the past three years that push forward the frontier of our understanding regarding sorting circuits, including new upper- and lower-bounds. 

In her talk, she shows how to construct an O(n k)-sized sorting circuit that sorts n elements each with a k-bit key, and also a matching lower bound showing its optimality for every k. 

This result is surprising due to the following known barriers. 

First, Donald Knuth’s famous 1973 textbook describes how comparison-based sorting algorithms could not achieve o(n log n) size even for 1-bit keys. In 2019 LSX and AFKL added to our understanding by proving how we could not achieve o(n log n)-sized sorting circuits, even for 1-bit keys, if we required stability (even if forgoing the comparison-based requirement).

Dr Shi’s approach is the first to show any non-trivial result using non-comparison-based techniques in the circuit model.

For the full transcript of Elaine Shi’s Chen’s presentation, click here.

To learn more about the algorithms and other details behind her work, watch Dr. Shi’s full presentation below.