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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
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

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WJ0-45J597Y-7&_user=651519&_coverDate=08%2F31%2F1998&_alid=565133398&_rdoc=2&_fmt=summary&_orig=search&_cdi=6864&_sort=d&_docanchor=&view=c&_ct=2&_acct=C000035158&_version=1&_urlVersion=0&_userid=651519&md5=ff3babae6038164af930b1cd2174d2fb

Authority records BETA

Andersson, Arne

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 444 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf