uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Sorting in linear time?
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Mathematics and Computer Science, Department of Information Technology. Faculty of Science and Technology, Biology, Department of Ecology and Evolution, Computing Science.
1998 (English)In: Journal of Computer and System Sciences, Vol. 57, 74-93 p.Article in journal (Refereed) Published
Abstract [en]

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range 0 .. 2^(w-1) in O(n loglog n) time, for arbitrary w >= log n, a significant improvement over the bound of O(n sqrt(log n)) achieved by the fusion trees of Fredman and Willard. Provided that w >= (log n)^(2+epsilon) for some fixed epsilon>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-cost PRAM with a word length of w bits. The first one yields an algorithm that uses O(log n) time and O(n loglog n) operations on a deterministic CRCW PRAM. The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w >= (log n)^(2+epsilon) for some fixed epsilon>0.

Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

Place, publisher, year, edition, pages
1998. Vol. 57, 74-93 p.
Keyword [en]
sorting algorithms
URN: urn:nbn:se:uu:diva-25784OAI: oai:DiVA.org:uu-25784DiVA: diva2:53558
Available from: 2007-04-18 Created: 2007-04-18 Last updated: 2011-01-14

Open Access in DiVA

No full text

Other links


Search in DiVA

By author/editor
Andersson, Arne
By organisation
Department of Information TechnologyComputing Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 205 hits
ReferencesLink to record
Permanent link

Direct link