More Efficient Parallel Integer Sorting

Yijie Han; Xin He

doi:10.1142/S0129054122500071

More Efficient Parallel Integer Sorting

Yijie Han
, Xin He

Department of Computer Science and Engineering

University of Missouri at Kansas City

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2,..,n1/2} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2) operations. It also sorts n integers in {0, 1, 2,..,n-1} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2logloglog n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O(n(log n)1/2).

Original language	English
Pages (from-to)	411-427
Number of pages	17
Journal	International Journal of Foundations of Computer Science
Volume	33
Issue number	5
DOIs	https://doi.org/10.1142/S0129054122500071
State	Published - Aug 1 2022

Keywords

Algorithms
bucket sorting
design of algorithms
integer sorting
PRAM algorithms

Access to Document

10.1142/S0129054122500071

Cite this

@article{9c4461c55cfc4717b3eb866de3a19d60,

title = "More Efficient Parallel Integer Sorting",

abstract = "We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in \{0, 1, 2,..,n1/2\} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2) operations. It also sorts n integers in \{0, 1, 2,..,n-1\} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2logloglog n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O(n(log n)1/2).",

keywords = "Algorithms, bucket sorting, design of algorithms, integer sorting, PRAM algorithms",

author = "Yijie Han and Xin He",

note = "Publisher Copyright: {\textcopyright} 2022 World Scientific Publishing Company.",

year = "2022",

month = aug,

day = "1",

doi = "10.1142/S0129054122500071",

language = "English",

volume = "33",

pages = "411--427",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

T1 - More Efficient Parallel Integer Sorting

AU - Han, Yijie

AU - He, Xin

PY - 2022/8/1

Y1 - 2022/8/1

N2 - We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2,..,n1/2} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2) operations. It also sorts n integers in {0, 1, 2,..,n-1} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2logloglog n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O(n(log n)1/2).

AB - We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2,..,n1/2} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2) operations. It also sorts n integers in {0, 1, 2,..,n-1} in O((log n)3/2/loglog n) time and O(n(log n/loglog n)1/2logloglog n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O(n(log n)1/2).

KW - Algorithms

KW - bucket sorting

KW - design of algorithms

KW - integer sorting

KW - PRAM algorithms

UR - https://www.scopus.com/pages/publications/85127880453

U2 - 10.1142/S0129054122500071

DO - 10.1142/S0129054122500071

M3 - Article

AN - SCOPUS:85127880453

SN - 0129-0541

VL - 33

SP - 411

EP - 427

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 5

ER -

More Efficient Parallel Integer Sorting

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this