Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort.
- Resource Type
- Article
- Authors
- Ganapathi, Pramod; Chowdhury, Rezaul
- Source
- Computer Journal. Oct2022, Vol. 65 Issue 10, p2709-2719. 11p.
- Subject
- *COMPUTATIONAL complexity
*ALGORITHMS
*PARALLEL algorithms
- Language
- ISSN
- 0010-4620
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 |${{\mathcal{O}}}\left ({n^{\log _2 3}}\right)$| in contrast to |${{\mathcal{O}}}\left ({n^2}\right)$| of standard insertion sort. [ABSTRACT FROM AUTHOR]