In the paper, the authors present a tight conditional lower bound on the complexity of external memory sorting of integers. Their lower bound is based on a famous conjecture in network coding by Li and Li, who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs.

Abstract:

Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus, external memory sorting algorithms, first introduced by Aggarwal and Vitter, are often used. The complexity of comparison-based external memory sorting has been understood for decades by now; however, the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lg n) bits each in O(n) time using the classic Radix Sort algorithm; however, in external memory, there are no faster integer sorting algorithms known than the simple comparison-based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.

Read the full article from 10/2020 Communications of the ACM (vol. 63, no.10), here: https://cacm.acm.org/magazines/2020/10/247602-lower-bounds-for-external-memory-integer-sorting-via-network-coding/fulltext