Sorting in Linear Time?Arne Andersson*Torben HageruptAbstractWe show that a unit-cost RAM with a word length of w bitscan sort n integers in the range O. . 2W – 1 in O (n log log n)time, for arbitrary w z log n, a significant improvementover the bound of O (n-) achieved by the fusion treesof Fredman and Willard. Provided that w 2 (log n)z+’, forsome fixed e > 0, the sorting can even be accomplished inlinear expected time with a randomized algorithm.Both of our algorithms parallelize without loss on a unit-cost PRAM with a word length of w bits. The first one yieldsan algorithm that uses O (log n) time and O (n log log n) op-erations on a deterministic CRCW PRAM. The second oneyields an algorithm that uses O(log n) expected time andO(n) expected operations on a randomized EREW PRAM,provided that w 2 (log n)2+’ for some fixed c >0.Our deterministic and randomized sequential and parallelalgorithms generalize to the lexicographic sorting problemof sorting multiple-precision integers represented in severalwords.1 IntroductionSorting is one of the most fundamental computational prob-lems, and n keys can be sorted in O(n logn) time by anyof a number of “well-known sorting algorithms. These algo-rithms operate in the comparison-based setting, i.e., they ob-tain information about the relative order of keys exclusivelythrough pairwise comparisons. It is easy to show that a run-ning time of O (n log n) is optimal in the comparison-basedmodel. However, this model may not always be the mostnatural one for the study of sorting problems, since real ma-chines allow many other operations besides comparison. Us-ing indirect addressing, for instance, it is possible to sortn* Department of Computer Science, Lund University, Box 118, S–22 100Lund, Sweden. arne@dna. lth. se, stef an@dna. lth. sef M~-pl~~k.In~tit”t fur Infomatik, DJ56123 s~brijcken, Germany.Supported by the ESPRIT BssicResesrchActions Progmm of the EU un-der contract No. 7141 (project ALCOM II). torben@mpi-sb. mpg. dei DeP@ment of Computer science,fing’s college London, .%-and, Lon-don WC2R 2LS, U. K. raman@dcs. kcl. ac .ukPermission to copy without fee all or part of this material isgranted provided that the copies are not made or distributed fordirect commercial advantaqe, the ACM copyri ht notice and the8“title of the publication and.lts date appear, an notice is giventhat copymis by permission of the Association of ComputingMachinery. o cop otherwise, or to republish, requiresf ra fee anctlor specI C permission.STOC’ 95, Las V as, Nevada, USAY@ 1995 ACM O-89. 91-718-9195/0005..$3 .50Stefan Nilsson*Rajeev Ramam~integers in the range O.. n – 1 in linear time via bucket sort-ing, thereby demonstrating that the comparison-based lowerbound can be meaningless in the context of integer sorting.Integer sorting is not an exotic special case, but in factis one of the sorting problems most frequently encountered.Aside from the ubiquity of integers in algorithms of all kinds,we note that all objects manipulated by a ccmventional com-puter are represented internally by bit patterns that are inter-preted as integers by the built-in arithmetic instructions. Formost basic data types, the numerical ordering of the repre-senting integers induces a natural ordering on the objects rep-resented; e.g., if an integer represents a character string in thenatural way, the induced ordering is the lexicographic order-ing among character strings. This is true even for floating-point numbers; indeed, the IEEE 754 floating-point standardwas designed specifically to facilitate the scwting of floating-point numbers by means of integer-sorting subroutines [13,p. 228]. Most sorting problems therefore eventually boildown to sorting integers or, possibly, multiple-precision in-tegers stored in several words.Classical algorithms for integer sorting require assump-tions about the size of the integers to be sorted, or else have arunning time dependent on the size. Bucket sorting requiresthe n input keys to be in the range O.. n – 1. Radix sortingin k phases, each phase implemented via bucket sorting, cansort n integers in the range O. .nk – 1 in O (T&) time. A moresophisticated technique, due to Kirkpatrick and Reisch [14],reduces this to O(n log k), but the fact remains that as the sizeof the integers to be sorted grows to infinity, the cost of thesorting also grows to infinity (or to @(n log n), if we switchto a comparison-based method at the appropriate point).If we allow intermediate results containing many more bitsthan the input numbers, we can actually sort integers in lineartime independently of their size, as demonstrated by Paul andSimon [18] and Kirkpatrick and Reisch [14]. But again, froma practical point of view, this is not what we want, since a realmachine is unlikely to have unit-time instructions for operat-ing on integers containing a huge number (of bits. Instead, ifthe input numbers are w-bit integers, we would like all inter-mediate results computed by a sorting algorithm to fit in wbits as well—in the terminology of Kirkpatrick and Reisch,the algorithm should be conservative. In this case it is real-istic to assume that a full repertoire of “reasonable” instrttc-tions can be applied to word-sized operands in constant time.In the remainder of the paper, when nothing else is stated, wewill take “sorting” to mean sorting w-bit words on a unit-costRAM with a word length of w bits.427Fredman and Willard [9] were the first to show that n arbi-trary integers can be sorted in o(n log n) time by a conserva-tive method. Their algorithm, based on fusion trees, sorts nintegers in O (n=) time. We describe two simple algo-rithms that improve their result. It should be noted that fusiontrees have other uses besides sorting, such as in efficient datastructures, to which our results do not apply.Our first algorithm works in O(n log log n) time. It usesarithmetic instructions drawn from what we call the restrictedinstruction set, including comparison, addition, subtraction,bitwiseAND and OR, and unrestricted bit shift, i.e., shift of anentire word by a number of bit positions specified in a secondword. As is not difficult to see, these instructions are all inACO, i.e., they can be implemented through constant-depth,polynomial-size circuits with unbounded fan-in. Since this isknown not to be the case for the multiplication instruction [4],which is essential for the fusion-tree algorithm, our algorithmcan also be viewed as placing