Sorting in Linear Time Torben Hagerupt Arne Andersson Abstract Rajeev Ramam Stefan Nilsson integers in the range O n 1 in linear time via bucket sorting thereby demonstrating We show that a unit cost RAM with a word length of w bits can sort n integers in the range O 2W 1 in O n log log n time for arbitrary w z log n a significant improvement over the bound of O n achieved by the fusion trees of Fredman and Willard Provided that w 2 log n z for some fixed e 0 the sorting can even be accomplished in linear expected time with a randomized algorithm Both of our algorithms parallelize without loss on a unit that the comparison based lower bound can be meaningless in the context of integer sorting Integer sorting is not an exotic special case but in fact is 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 computer are represented internally by bit patterns that are interpreted as integers by the built in arithmetic most basic data types the numerical instructions ordering For of the repre cost PRAM with a word length of w bits The first one yields senting integers induces a natural ordering on the objects rep an algorithm resented e g if an integer represents a character string in the that uses O log n time and O n log log n op erations on a deterministic yields an algorithm CRCW PRAM The second one that uses O log n expected time and O 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 parallel algorithms generalize to the lexicographic sorting problem of sorting multiple precision integers represented in several natural way the induced ordering is the lexicographic ing among character strings point numbers indeed the IEEE 754 floating point down to sorting integers or possibly multiple precision ning time of O n log n is optimal sophisticated technique due to Kirkpatrick and Reisch 14 reduces this to O n log k but the fact remains that as the size of the integers to be sorted grows to infinity the cost of the sorting also grows to infinity in the comparison based to a comparison based this model may not always be the most natural one for the study of sorting problems addressing of Computer Science Lund University by the ESPRIT Bssic ResesrchActions der contract No 7141 project ALCOM i DeP ment of Computer science time independently don WC2R 2LS U K raman dcs kcl Germany of their size as demonstrated by Paul and ing on integers containing a huge number of bits Instead if the input numbers are w bit integers we would like all inter Progmm of the EU un II torben mpi sb point many more bits Simon 18 and Kirkpatrick and Reisch 14 But again from a practical point of view this is not what we want since a real machine is unlikely to have unit time instructions for operat Box 118 S 22 100 fing s college London results containing than the input numbers we can actually sort integers in linear Us for instance it is possible to sort n Lund Sweden arne dna lth se stef an dna lth se f M pl k In tit t fur Infomatik DJ56123 s brijcken or to n log n if we switch method at the appropriate If we allow intermediate since real ma chines allow many other operations besides comparison Department assump the n input keys to be in the range O n 1 Radix sorting in k phases each phase implemented via bucket sorting can sort n integers in the range O nk 1 in O T time A more of a number of well known sorting algorithms These algorithms operate in the comparison based setting i e they obtain information about the relative order of keys exclusively through pairwise comparisons It is easy to show that a run ing indirect for integer sorting require running time dependent on the size Bucket sorting requires Sorting is one of the most fundamental computational problems and n keys can be sorted in O n log n time by any However algorithms tions about the size of the integers to be sorted or else have a Introduction Supported in tegers stored in several words Classical model standard was designed specifically to facilitate the scwting of floatingpoint numbers by means of integer sorting subroutines 13 p 228 Most sorting problems therefore eventually boil words 1 order This is true even for floating mpg de and Lon mediate results computed by a sorting algorithm to fit in w bits as well in the terminology of Kirkpatrick and Reisch ac uk the algorithm Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantaqe the ACM copyri ht notice and the title of the publication and lts date appear an 8 notice is given that copym is by permission of the Association of Computing Machinery o cop otherwise or to republish requires f specIr C permission a fee anctlor STOC 95 Las V as Nevada USA Y 91 718 9195 0005 3 50 1995 ACM O 89 should be conservative istic to assume that a full repertoire In this case it is real 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 we will take sorting to mean sorting w bit words on a unit cost RAM with a word length of w bits 427 Fredman and Willard optimal if N fl n log log n 9 were the first to show that n arbi Our results flow from the combination trary integers can be sorted in o n log n time by a conservative method Their algorithm integers in O n niques of packed based on fusion trees sorts n in 12 and 2 saves on integer sorting by packing several integers into a single word and operating simultaneously on trees have other uses besides sorting such as in efficient data all of them at unit cost This is only possible of course if several integers to be sorted fit in one word i e packed sorting is inherently nonconservative Range reduction on the structures to which our results do not apply Our first algorithm works in O n log log n time It uses arithmetic instructions drawn from what we call the restricted instruction set including comparison addition subtraction and AND OR other hand reduces the problem of sorting integers in a certain range to that of sorting integers in a smaller range The and unrestricted bit shift i e shift of an combination entire word by a number of bit positions specified in a second word As is not difficult to see these instructions are all in ACO i e they can be implemented