Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort

Pramod Ganapathi; Rezaul Chowdhury

doi:10.1093/comjnl/bxab107

Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort

Computer Science

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

6 Scopus citations

Abstract

We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is O(n^log₂³) in contrast to O(n²) of standard insertion sort.

Original language	English
Pages (from-to)	2709-2719
Number of pages	11
Journal	Computer Journal
Volume	65
Issue number	10
DOIs	https://doi.org/10.1093/comjnl/bxab107
State	Published - Oct 1 2022

Keywords

bubble sort
insertion sort
merge sort
parallel divide-and-conquer
quicksort
selection sort
sorting algorithm

Access to Document

10.1093/comjnl/bxab107

Cite this

@article{f9fd23e5aa2f46d2b9fc3feb99eaeade,

title = "Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort",

abstract = "We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is O(nlog23) in contrast to O(n2) of standard insertion sort.",

keywords = "bubble sort, insertion sort, merge sort, parallel divide-and-conquer, quicksort, selection sort, sorting algorithm",

author = "Pramod Ganapathi and Rezaul Chowdhury",

year = "2022",

month = oct,

day = "1",

doi = "10.1093/comjnl/bxab107",

language = "English",

volume = "65",

pages = "2709--2719",

journal = "Computer Journal",

issn = "0010-4620",

number = "10",

}

TY - JOUR

T1 - Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort

AU - Ganapathi, Pramod

AU - Chowdhury, Rezaul

PY - 2022/10/1

Y1 - 2022/10/1

N2 - We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is O(nlog23) in contrast to O(n2) of standard insertion sort.

AB - We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is O(nlog23) in contrast to O(n2) of standard insertion sort.

KW - bubble sort

KW - insertion sort

KW - merge sort

KW - parallel divide-and-conquer

KW - quicksort

KW - selection sort

KW - sorting algorithm

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

U2 - 10.1093/comjnl/bxab107

DO - 10.1093/comjnl/bxab107

M3 - Article

AN - SCOPUS:85124498802

SN - 0010-4620

VL - 65

SP - 2709

EP - 2719

JO - Computer Journal

JF - Computer Journal

IS - 10

ER -

Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this