Lower bounds for external memory integer sorting via network coding

Sorting extremely large datasets is a frequently occuring 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 (1988), 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.

Authors

• Alireza Farhadi 0001
• MohammadTaghi Hajiaghayi
• Kasper Green Larsen
• Elaine Shi

Keywords

• Lower Bounds
• Integer Sorting
• Reductions
• External Memory
• Network Coding