Sort Integers into a Linked List Article Swipe

PDF

Yijie Han , Hemasree Koganti , Nikita Goyal ·

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.5539/cis.v13n1p51

We show that n integers in {0, 1, …, m-1} can be sorted into a linked list in constant time using nlogm processors on the Priority CRCW PRAM model, and they can be sorted into a linked list in O(loglogm/logt) time using nt processors on the Priority CRCW PRAM model.

Related Topics

Concepts

Computer science sort Constant (computer programming) Parallel computing Arithmetic Algorithm Mathematics Information retrieval Programming language

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.5539/cis.v13n1p51
PDF: http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444
OA Status: diamond
Cited By: 2
References: 12
Related Works: 10
OpenAlex ID: https://openalex.org/W2998979141

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2998979141

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.5539/cis.v13n1p51

Digital Object Identifier
Title: Sort Integers into a Linked List

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-01-13

Full publication date if available
Authors: Yijie Han, Hemasree Koganti, Nikita Goyal

List of authors in order
Landing page: https://doi.org/10.5539/cis.v13n1p51

Publisher landing page
PDF URL: https://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: diamond

Open access status per OpenAlex
OA URL: https://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444

Direct OA link when available
Concepts: Computer science, sort, Constant (computer programming), Parallel computing, Arithmetic, Algorithm, Mathematics, Information retrieval, Programming language

Top concepts (fields/topics) attached by OpenAlex
Cited by: 2

Total citation count in OpenAlex
Citations by year (recent): 2022: 1, 2021: 1

Per-year citation counts (last 5 years)
References (count): 12

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2998979141
doi	https://doi.org/10.5539/cis.v13n1p51
ids.doi	https://doi.org/10.5539/cis.v13n1p51
ids.mag	2998979141
ids.openalex	https://openalex.org/W2998979141
fwci	0.29417621
type	article
title	Sort Integers into a Linked List
biblio.issue	1
biblio.volume	13
biblio.last_page	51
biblio.first_page	51
topics[0].id	https://openalex.org/T10720
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9998999834060669
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Complexity and Algorithms in Graphs
topics[1].id	https://openalex.org/T11269
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9998000264167786
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1702
topics[1].subfield.display_name	Artificial Intelligence
topics[1].display_name	Algorithms and Data Compression
topics[2].id	https://openalex.org/T12072
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9991999864578247
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1702
topics[2].subfield.display_name	Artificial Intelligence
topics[2].display_name	Machine Learning and Algorithms
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.854496955871582
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C88548561
concepts[1].level	2
concepts[1].score	0.7177680730819702
concepts[1].wikidata	https://www.wikidata.org/wiki/Q347599
concepts[1].display_name	sort
concepts[2].id	https://openalex.org/C2777027219
concepts[2].level	2
concepts[2].score	0.5629234910011292
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1284190
concepts[2].display_name	Constant (computer programming)
concepts[3].id	https://openalex.org/C173608175
concepts[3].level	1
concepts[3].score	0.4984865188598633
concepts[3].wikidata	https://www.wikidata.org/wiki/Q232661
concepts[3].display_name	Parallel computing
concepts[4].id	https://openalex.org/C94375191
concepts[4].level	1
concepts[4].score	0.4017893671989441
concepts[4].wikidata	https://www.wikidata.org/wiki/Q11205
concepts[4].display_name	Arithmetic
concepts[5].id	https://openalex.org/C11413529
concepts[5].level	1
concepts[5].score	0.35239046812057495
concepts[5].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[5].display_name	Algorithm
concepts[6].id	https://openalex.org/C33923547
concepts[6].level	0
concepts[6].score	0.1431485116481781
concepts[6].wikidata	https://www.wikidata.org/wiki/Q395
concepts[6].display_name	Mathematics
concepts[7].id	https://openalex.org/C23123220
concepts[7].level	1
concepts[7].score	0.12609711289405823
concepts[7].wikidata	https://www.wikidata.org/wiki/Q816826
concepts[7].display_name	Information retrieval
concepts[8].id	https://openalex.org/C199360897
concepts[8].level	1
concepts[8].score	0.11295074224472046
concepts[8].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[8].display_name	Programming language
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.854496955871582
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/sort
keywords[1].score	0.7177680730819702
keywords[1].display_name	sort
keywords[2].id	https://openalex.org/keywords/constant
keywords[2].score	0.5629234910011292
keywords[2].display_name	Constant (computer programming)
keywords[3].id	https://openalex.org/keywords/parallel-computing
keywords[3].score	0.4984865188598633
keywords[3].display_name	Parallel computing
keywords[4].id	https://openalex.org/keywords/arithmetic
keywords[4].score	0.4017893671989441
keywords[4].display_name	Arithmetic
keywords[5].id	https://openalex.org/keywords/algorithm
keywords[5].score	0.35239046812057495
keywords[5].display_name	Algorithm
keywords[6].id	https://openalex.org/keywords/mathematics
keywords[6].score	0.1431485116481781
keywords[6].display_name	Mathematics
keywords[7].id	https://openalex.org/keywords/information-retrieval
keywords[7].score	0.12609711289405823
keywords[7].display_name	Information retrieval
keywords[8].id	https://openalex.org/keywords/programming-language
keywords[8].score	0.11295074224472046
keywords[8].display_name	Programming language
language	en
locations[0].id	doi:10.5539/cis.v13n1p51
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S2764452479
locations[0].source.issn	1913-8989, 1913-8997
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	1913-8989
locations[0].source.is_core	True
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Computer and Information Science
locations[0].source.host_organization	https://openalex.org/P4310322531
locations[0].source.host_organization_name	Canadian Center of Science and Education
locations[0].source.host_organization_lineage	https://openalex.org/P4310322531
locations[0].source.host_organization_lineage_names	Canadian Center of Science and Education
locations[0].license	cc-by
locations[0].pdf_url	http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	Computer and Information Science
locations[0].landing_page_url	https://doi.org/10.5539/cis.v13n1p51
indexed_in	crossref
authorships[0].author.id	https://openalex.org/A5091329448
authorships[0].author.orcid	https://orcid.org/0000-0003-1305-6815
authorships[0].author.display_name	Yijie Han
authorships[0].countries	US
authorships[0].affiliations[0].institution_ids	https://openalex.org/I75421653
authorships[0].affiliations[0].raw_affiliation_string	School of Computing and Engineering, University of Missouri at Kansas City, United States
authorships[0].institutions[0].id	https://openalex.org/I75421653
authorships[0].institutions[0].ror	https://ror.org/01w0d5g70
authorships[0].institutions[0].type	education
authorships[0].institutions[0].lineage	https://openalex.org/I75421653
authorships[0].institutions[0].country_code	US
authorships[0].institutions[0].display_name	University of Missouri–Kansas City
authorships[0].author_position	first
authorships[0].raw_author_name	Yijie Han
authorships[0].is_corresponding	False
authorships[0].raw_affiliation_strings	School of Computing and Engineering, University of Missouri at Kansas City, United States
authorships[1].author.id	https://openalex.org/A5026082116
authorships[1].author.orcid
authorships[1].author.display_name	Hemasree Koganti
authorships[1].countries	US
authorships[1].affiliations[0].institution_ids	https://openalex.org/I75421653
authorships[1].affiliations[0].raw_affiliation_string	School of Computing and Engineering, University of Missouri at Kansas City, United States
authorships[1].institutions[0].id	https://openalex.org/I75421653
authorships[1].institutions[0].ror	https://ror.org/01w0d5g70
authorships[1].institutions[0].type	education
authorships[1].institutions[0].lineage	https://openalex.org/I75421653
authorships[1].institutions[0].country_code	US
authorships[1].institutions[0].display_name	University of Missouri–Kansas City
authorships[1].author_position	middle
authorships[1].raw_author_name	Hemasree Koganti
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	School of Computing and Engineering, University of Missouri at Kansas City, United States
authorships[2].author.id	https://openalex.org/A5026787491
authorships[2].author.orcid
authorships[2].author.display_name	Nikita Goyal
authorships[2].countries	US
authorships[2].affiliations[0].institution_ids	https://openalex.org/I75421653
authorships[2].affiliations[0].raw_affiliation_string	School of Computing and Engineering, University of Missouri at Kansas City, United States
authorships[2].institutions[0].id	https://openalex.org/I75421653
authorships[2].institutions[0].ror	https://ror.org/01w0d5g70
authorships[2].institutions[0].type	education
authorships[2].institutions[0].lineage	https://openalex.org/I75421653
authorships[2].institutions[0].country_code	US
authorships[2].institutions[0].display_name	University of Missouri–Kansas City
authorships[2].author_position	last
authorships[2].raw_author_name	Nikita Goyal
authorships[2].is_corresponding	False
authorships[2].raw_affiliation_strings	School of Computing and Engineering, University of Missouri at Kansas City, United States
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Sort Integers into a Linked List
has_fulltext	True
is_retracted	False
updated_date	2025-12-06T23:10:59.065948
primary_topic.id	https://openalex.org/T10720
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9998999834060669
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Complexity and Algorithms in Graphs
related_works	https://openalex.org/W2361805396, https://openalex.org/W2972254340, https://openalex.org/W2051487156, https://openalex.org/W2073681303, https://openalex.org/W2022231341, https://openalex.org/W1805912688, https://openalex.org/W4255476312, https://openalex.org/W2373973507, https://openalex.org/W4250902763, https://openalex.org/W2351154965
cited_by_count	2
counts_by_year[0].year	2022
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2021
counts_by_year[1].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.5539/cis.v13n1p51
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S2764452479
best_oa_location.source.issn	1913-8989, 1913-8997
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	1913-8989
best_oa_location.source.is_core	True
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Computer and Information Science
best_oa_location.source.host_organization	https://openalex.org/P4310322531
best_oa_location.source.host_organization_name	Canadian Center of Science and Education
best_oa_location.source.host_organization_lineage	https://openalex.org/P4310322531
best_oa_location.source.host_organization_lineage_names	Canadian Center of Science and Education
best_oa_location.license	cc-by
best_oa_location.pdf_url	http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	Computer and Information Science
best_oa_location.landing_page_url	https://doi.org/10.5539/cis.v13n1p51
primary_location.id	doi:10.5539/cis.v13n1p51
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S2764452479
primary_location.source.issn	1913-8989, 1913-8997
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	1913-8989
primary_location.source.is_core	True
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Computer and Information Science
primary_location.source.host_organization	https://openalex.org/P4310322531
primary_location.source.host_organization_name	Canadian Center of Science and Education
primary_location.source.host_organization_lineage	https://openalex.org/P4310322531
primary_location.source.host_organization_lineage_names	Canadian Center of Science and Education
primary_location.license	cc-by
primary_location.pdf_url	http://www.ccsenet.org/journal/index.php/cis/article/download/0/0/41815/43444
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	Computer and Information Science
primary_location.landing_page_url	https://doi.org/10.5539/cis.v13n1p51
publication_date	2020-01-13
publication_year	2020
referenced_works	https://openalex.org/W1992470151, https://openalex.org/W2047234016, https://openalex.org/W1966913545, https://openalex.org/W1978560871, https://openalex.org/W2057697239, https://openalex.org/W2053601995, https://openalex.org/W2947147515, https://openalex.org/W1584086289, https://openalex.org/W2054284059, https://openalex.org/W1534829670, https://openalex.org/W2395933225, https://openalex.org/W2153480667
referenced_works_count	12
abstract_inverted_index.a	14, 35
abstract_inverted_index.n	3
abstract_inverted_index.1,	7
abstract_inverted_index.We	0
abstract_inverted_index.be	11, 32
abstract_inverted_index.in	5, 17, 38
abstract_inverted_index.nt	42
abstract_inverted_index.on	23, 44
abstract_inverted_index.and	29
abstract_inverted_index.can	10, 31
abstract_inverted_index.the	24, 45
abstract_inverted_index.{0,	6
abstract_inverted_index.CRCW	26, 47
abstract_inverted_index.PRAM	27, 48
abstract_inverted_index.into	13, 34
abstract_inverted_index.list	16, 37
abstract_inverted_index.m-1}	9
abstract_inverted_index.show	1
abstract_inverted_index.that	2
abstract_inverted_index.they	30
abstract_inverted_index.time	19, 40
abstract_inverted_index.nlogm	21
abstract_inverted_index.using	20, 41
abstract_inverted_index.linked	15, 36
abstract_inverted_index.model,	28
abstract_inverted_index.model.	49
abstract_inverted_index.sorted	12, 33
abstract_inverted_index.Priority	25, 46
abstract_inverted_index.constant	18
abstract_inverted_index.integers	4
abstract_inverted_index.processors	22, 43
abstract_inverted_index.&hellip;,	8
abstract_inverted_index.O(loglogm/logt)	39
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	3
citation_normalized_percentile.value	0.6010296
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False