Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort. (2nd August 2021)

• Record Type: Journal Article
• Authors: Ganapathi, Pramod; Chowdhury, Rezaul
• Is Part Of: Computer journal. Volume 65:Number 10(2022)
• Page Start: 2709
• Page End: 2719
• Publication Date: 2021-08-02
• Subjects: parallel divide-and-conquer -- sorting algorithm -- bubble sort -- selection sort -- insertion sort -- merge sort -- quicksort; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab107
• Languages: English
• ISSNs: 0010-4620

Abstract

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 ${{\mathcal{O}}}\left ({n^{\log _2 3}}\right )$ in contrast to ${{\mathcal{O}}}\left ({n^2}\right )$ of standard insertion sort.