uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Sorting in linear time?
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi. Teknisk-naturvetenskapliga fakulteten, Biologiska sektionen, Institutionen för ekologi och evolution, Datalogi.
1998 (Engelska)Ingår i: Journal of Computer and System Sciences, Vol. 57, s. 74-93Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
1998. Vol. 57, s. 74-93
Nyckelord [en]
sorting algorithms
Identifikatorer
URN: urn:nbn:se:uu:diva-25784OAI: oai:DiVA.org:uu-25784DiVA, id: diva2:53558
Tillgänglig från: 2007-04-18 Skapad: 2007-04-18 Senast uppdaterad: 2011-01-14

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

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

Personposter BETA

Andersson, Arne

Sök vidare i DiVA

Av författaren/redaktören
Andersson, Arne
Av organisationen
Institutionen för informationsteknologiDatalogi

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 826 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf