2016/08/30 by Alexandros V. Gerbessiotis, Gerbessiotis, Alexandros V
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #68W40 #68W99 #Algorithms and Data Compression #DNA and Biological Computing #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Parallel Computing and Optimization Techniques #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1608.08648
openalex publication_date 2016/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose new sequential sorting operations by adapting techniques and\nmethods used for designing parallel sorting algorithms. Although the norm is to\nparallelize a sequential algorithm to improve performance, we adapt a\ncontrarian approach: we employ parallel computing techniques to speed up\nsequential sorting. Our methods can also work for multi-core sorting with minor\nadjustments that do not necessarily require full parallelization of the\noriginal sequential algorithm. The proposed approach leads to the development\nof asymptotically efficient deterministic and randomized sorting operations\nwhose practical sequential and multi-core performance, as witnessed by an\nexperimental study, matches or surpasses existing optimized sorting algorithm\nimplementations.\n We utilize parallel sorting techniques such as deterministic regular sampling\nand random oversampling. We extend the notion of deterministic regular sampling\ninto deterministic regular oversampling for sequential and multi-core sorting\nand demonstrate its potential. We then show how these techniques can be used\nfor sequential sorting and also lead to better multi-core sorting algorithm\nperformance as witnessed by the undertaken experimental study.\n