# An 0(n log n) sorting network URL: https://dl.acm.org/doi/10.1145/800061.808726 Authors: M. Ajtai, J. Komlós, E. Szemerédi ## Abstract The purpose of this paper is to describe a sorting network of size O(n log n) and depth O(log n). A natural way of sorting is through consecutive halvings: determine the upper and lower halves of the set, proceed similarly within the halves, and so on. Unfortunately, while one can halve a set using only O(n) comparisons, this cannot be done in less than log n (parallel) time, and it is known that a halving network needs (1/2)n log n comparisons. It is possible, however, to construct a network of O(n) comparisons which halves in constant time with high accuracy. This procedure (ε-halving) and a derived procedure (ε-nearsort) are described below, and our sorting network will be centered around these elementary steps.