Sorting Short Integers: The Exposition

Michal Koucký, The Computational Complexity Column by Michal Koucky ́


This expository article reviews recent and some not so recent results on sorting integers in various models of computation: from word RAM to Boolean circuits, with the main focus on the latter. We hope that even seasoned researcher will find our perspective refreshing.

Full Text:



  • There are currently no refbacks.