Parallel Merging and Sorting on Linked List Article Swipe

PDF

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.24203/ijcit.v10i2.85

We study linked list sorting and merging on the PRAM model. In this paper we show that n real numbers can be sorted into a linked list in constant time with n2+e processors or in ) time with n2 processors. We also show that two sorted linked lists of n integers in {0, 1, …, m} can be merged into one sorted linked list in O(log(c)n(loglogm)1/2) time using n/(log(c)n(loglogm)1/2) processors, where c is an arbitrarily large constant.

Related Topics

Concepts

Sorting Constant (computer programming) Computer science Parallel computing Binary logarithm Combinatorics Sorting algorithm Linked list Arithmetic Mathematics Algorithm Programming language

Metadata

Type: article
Language: en
Landing Page: https://doi.org/10.24203/ijcit.v10i2.85
PDF: https://www.ijcit.com/index.php/ijcit/article/download/85/32
OA Status: diamond
Cited By: 1
References: 16
Related Works: 10
OpenAlex ID: https://openalex.org/W3156363310

All OpenAlex metadata

Raw OpenAlex JSON

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

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.24203/ijcit.v10i2.85

Digital Object Identifier
Title: Parallel Merging and Sorting on Linked List

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2021

Year of publication
Publication date: 2021-03-30

Full publication date if available
Authors: Yijie Han, Sreevalli Tata

List of authors in order
Landing page: https://doi.org/10.24203/ijcit.v10i2.85

Publisher landing page
PDF URL: https://www.ijcit.com/index.php/ijcit/article/download/85/32

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.ijcit.com/index.php/ijcit/article/download/85/32

Direct OA link when available
Concepts: Sorting, Constant (computer programming), Computer science, Parallel computing, Binary logarithm, Combinatorics, Sorting algorithm, Linked list, Arithmetic, Mathematics, Algorithm, Programming language

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

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

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

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

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3156363310
doi	https://doi.org/10.24203/ijcit.v10i2.85
ids.doi	https://doi.org/10.24203/ijcit.v10i2.85
ids.mag	3156363310
ids.openalex	https://openalex.org/W3156363310
fwci	0.14110358
type	article
title	Parallel Merging and Sorting on Linked List
biblio.issue	2
biblio.volume	10
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11269
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/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Algorithms and Data Compression
topics[1].id	https://openalex.org/T12072
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9975000023841858
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	Machine Learning and Algorithms
topics[2].id	https://openalex.org/T12288
topics[2].field.id	https://openalex.org/fields/17
topics[2].field.display_name	Computer Science
topics[2].score	0.9975000023841858
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/1705
topics[2].subfield.display_name	Computer Networks and Communications
topics[2].display_name	Optimization and Search Problems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C111696304
concepts[0].level	2
concepts[0].score	0.8163646459579468
concepts[0].wikidata	https://www.wikidata.org/wiki/Q2303697
concepts[0].display_name	Sorting
concepts[1].id	https://openalex.org/C2777027219
concepts[1].level	2
concepts[1].score	0.6699466705322266
concepts[1].wikidata	https://www.wikidata.org/wiki/Q1284190
concepts[1].display_name	Constant (computer programming)
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.6141246557235718
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C173608175
concepts[3].level	1
concepts[3].score	0.5933533906936646
concepts[3].wikidata	https://www.wikidata.org/wiki/Q232661
concepts[3].display_name	Parallel computing
concepts[4].id	https://openalex.org/C63553672
concepts[4].level	2
concepts[4].score	0.5472986698150635
concepts[4].wikidata	https://www.wikidata.org/wiki/Q581168
concepts[4].display_name	Binary logarithm
concepts[5].id	https://openalex.org/C114614502
concepts[5].level	1
concepts[5].score	0.511987030506134
concepts[5].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[5].display_name	Combinatorics
concepts[6].id	https://openalex.org/C108094655
concepts[6].level	3
concepts[6].score	0.44481298327445984
concepts[6].wikidata	https://www.wikidata.org/wiki/Q181593
concepts[6].display_name	Sorting algorithm
concepts[7].id	https://openalex.org/C146101286
concepts[7].level	2
concepts[7].score	0.4226763844490051
concepts[7].wikidata	https://www.wikidata.org/wiki/Q7003418
concepts[7].display_name	Linked list
concepts[8].id	https://openalex.org/C94375191
concepts[8].level	1
concepts[8].score	0.3370905816555023
concepts[8].wikidata	https://www.wikidata.org/wiki/Q11205
concepts[8].display_name	Arithmetic
concepts[9].id	https://openalex.org/C33923547
concepts[9].level	0
concepts[9].score	0.32846590876579285
concepts[9].wikidata	https://www.wikidata.org/wiki/Q395
concepts[9].display_name	Mathematics
concepts[10].id	https://openalex.org/C11413529
concepts[10].level	1
concepts[10].score	0.30996429920196533
concepts[10].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[10].display_name	Algorithm
concepts[11].id	https://openalex.org/C199360897
concepts[11].level	1
concepts[11].score	0.09205114841461182
concepts[11].wikidata	https://www.wikidata.org/wiki/Q9143
concepts[11].display_name	Programming language
keywords[0].id	https://openalex.org/keywords/sorting
keywords[0].score	0.8163646459579468
keywords[0].display_name	Sorting
keywords[1].id	https://openalex.org/keywords/constant
keywords[1].score	0.6699466705322266
keywords[1].display_name	Constant (computer programming)
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.6141246557235718
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/parallel-computing
keywords[3].score	0.5933533906936646
keywords[3].display_name	Parallel computing
keywords[4].id	https://openalex.org/keywords/binary-logarithm
keywords[4].score	0.5472986698150635
keywords[4].display_name	Binary logarithm
keywords[5].id	https://openalex.org/keywords/combinatorics
keywords[5].score	0.511987030506134
keywords[5].display_name	Combinatorics
keywords[6].id	https://openalex.org/keywords/sorting-algorithm
keywords[6].score	0.44481298327445984
keywords[6].display_name	Sorting algorithm
keywords[7].id	https://openalex.org/keywords/linked-list
keywords[7].score	0.4226763844490051
keywords[7].display_name	Linked list
keywords[8].id	https://openalex.org/keywords/arithmetic
keywords[8].score	0.3370905816555023
keywords[8].display_name	Arithmetic
keywords[9].id	https://openalex.org/keywords/mathematics
keywords[9].score	0.32846590876579285
keywords[9].display_name	Mathematics
keywords[10].id	https://openalex.org/keywords/algorithm
keywords[10].score	0.30996429920196533
keywords[10].display_name	Algorithm
keywords[11].id	https://openalex.org/keywords/programming-language
keywords[11].score	0.09205114841461182
keywords[11].display_name	Programming language
language	en
locations[0].id	doi:10.24203/ijcit.v10i2.85
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4210225918
locations[0].source.issn	2279-0764
locations[0].source.type	journal
locations[0].source.is_oa	True
locations[0].source.issn_l	2279-0764
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	International Journal of Computer and Information Technology(2279-0764)
locations[0].source.host_organization
locations[0].source.host_organization_name
locations[0].license	cc-by-nc
locations[0].pdf_url	https://www.ijcit.com/index.php/ijcit/article/download/85/32
locations[0].version	publishedVersion
locations[0].raw_type	journal-article
locations[0].license_id	https://openalex.org/licenses/cc-by-nc
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name	International Journal of Computer and Information Technology(2279-0764)
locations[0].landing_page_url	https://doi.org/10.24203/ijcit.v10i2.85
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, USA
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, USA
authorships[1].author.id	https://openalex.org/A5085001141
authorships[1].author.orcid
authorships[1].author.display_name	Sreevalli Tata
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, USA
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	last
authorships[1].raw_author_name	Sreevalli Tata
authorships[1].is_corresponding	False
authorships[1].raw_affiliation_strings	School of Computing and Engineering, University of Missouri at Kansas City, USA
has_content.pdf	True
has_content.grobid_xml	True
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://www.ijcit.com/index.php/ijcit/article/download/85/32
open_access.oa_status	diamond
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Parallel Merging and Sorting on Linked List
has_fulltext	True
is_retracted	False
updated_date	2025-11-06T03:46:38.306776
primary_topic.id	https://openalex.org/T11269
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/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Algorithms and Data Compression
related_works	https://openalex.org/W2809748609, https://openalex.org/W3033694952, https://openalex.org/W2372558933, https://openalex.org/W2349288944, https://openalex.org/W797244100, https://openalex.org/W4298155039, https://openalex.org/W2801186172, https://openalex.org/W2367560286, https://openalex.org/W2181812531, https://openalex.org/W2368845094
cited_by_count	1
counts_by_year[0].year	2022
counts_by_year[0].cited_by_count	1
locations_count	1
best_oa_location.id	doi:10.24203/ijcit.v10i2.85
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4210225918
best_oa_location.source.issn	2279-0764
best_oa_location.source.type	journal
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l	2279-0764
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	International Journal of Computer and Information Technology(2279-0764)
best_oa_location.source.host_organization
best_oa_location.source.host_organization_name
best_oa_location.license	cc-by-nc
best_oa_location.pdf_url	https://www.ijcit.com/index.php/ijcit/article/download/85/32
best_oa_location.version	publishedVersion
best_oa_location.raw_type	journal-article
best_oa_location.license_id	https://openalex.org/licenses/cc-by-nc
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name	International Journal of Computer and Information Technology(2279-0764)
best_oa_location.landing_page_url	https://doi.org/10.24203/ijcit.v10i2.85
primary_location.id	doi:10.24203/ijcit.v10i2.85
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4210225918
primary_location.source.issn	2279-0764
primary_location.source.type	journal
primary_location.source.is_oa	True
primary_location.source.issn_l	2279-0764
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	International Journal of Computer and Information Technology(2279-0764)
primary_location.source.host_organization
primary_location.source.host_organization_name
primary_location.license	cc-by-nc
primary_location.pdf_url	https://www.ijcit.com/index.php/ijcit/article/download/85/32
primary_location.version	publishedVersion
primary_location.raw_type	journal-article
primary_location.license_id	https://openalex.org/licenses/cc-by-nc
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name	International Journal of Computer and Information Technology(2279-0764)
primary_location.landing_page_url	https://doi.org/10.24203/ijcit.v10i2.85
publication_date	2021-03-30
publication_year	2021
referenced_works	https://openalex.org/W2798579874, https://openalex.org/W2068862022, https://openalex.org/W2070570981, https://openalex.org/W6648388160, https://openalex.org/W2153480667, https://openalex.org/W2053601995, https://openalex.org/W2047234016, https://openalex.org/W2057697239, https://openalex.org/W2027679733, https://openalex.org/W6641965076, https://openalex.org/W6772406354, https://openalex.org/W1968477205, https://openalex.org/W1584086289, https://openalex.org/W2998979141, https://openalex.org/W3006590675, https://openalex.org/W2133673025
referenced_works_count	16
abstract_inverted_index.)	35
abstract_inverted_index.a	24
abstract_inverted_index.c	71
abstract_inverted_index.n	17, 49
abstract_inverted_index.1,	53
abstract_inverted_index.In	11
abstract_inverted_index.We	0, 40
abstract_inverted_index.an	73
abstract_inverted_index.be	21, 57
abstract_inverted_index.in	27, 34, 51, 64
abstract_inverted_index.is	72
abstract_inverted_index.m}	55
abstract_inverted_index.n2	38
abstract_inverted_index.of	48
abstract_inverted_index.on	7
abstract_inverted_index.or	33
abstract_inverted_index.we	14
abstract_inverted_index.and	5
abstract_inverted_index.can	20, 56
abstract_inverted_index.one	60
abstract_inverted_index.the	8
abstract_inverted_index.two	44
abstract_inverted_index.{0,	52
abstract_inverted_index.PRAM	9
abstract_inverted_index.also	41
abstract_inverted_index.into	23, 59
abstract_inverted_index.list	3, 26, 63
abstract_inverted_index.n2+e	31
abstract_inverted_index.real	18
abstract_inverted_index.show	15, 42
abstract_inverted_index.that	16, 43
abstract_inverted_index.this	12
abstract_inverted_index.time	29, 36, 66
abstract_inverted_index.with	30, 37
abstract_inverted_index.…,	54
abstract_inverted_index.large	75
abstract_inverted_index.lists	47
abstract_inverted_index.paper	13
abstract_inverted_index.study	1
abstract_inverted_index.using	67
abstract_inverted_index.where	70
abstract_inverted_index.linked	2, 25, 46, 62
abstract_inverted_index.merged	58
abstract_inverted_index.model.	10
abstract_inverted_index.sorted	22, 45, 61
abstract_inverted_index.merging	6
abstract_inverted_index.numbers	19
abstract_inverted_index.sorting	4
abstract_inverted_index.constant	28
abstract_inverted_index.integers	50
abstract_inverted_index.constant.	76
abstract_inverted_index.processors	32
abstract_inverted_index.arbitrarily	74
abstract_inverted_index.processors,	69
abstract_inverted_index.processors.	39
abstract_inverted_index.O(log(c)n(loglogm)1/2)	65
abstract_inverted_index.n/(log(c)n(loglogm)1/2)	68
cited_by_percentile_year.max	94
cited_by_percentile_year.min	89
countries_distinct_count	1
institutions_distinct_count	2
citation_normalized_percentile.value	0.52427033
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False