QR Sort: A Novel Non-Comparative Sorting Algorithm

Autor:	Bushman, Randolph T., Tebcherani, Tanya M., Yasin, Alhassan S.
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	In this paper, we introduce and prove QR Sort, a novel non-comparative integer sorting algorithm. This algorithm uses principles derived from the Quotient-Remainder Theorem and Counting Sort subroutines to sort input sequences stably. QR Sort exhibits the general time and space complexity $\mathcal{O}(n+d+\frac{m}{d})$, where $n$ denotes the input sequence length, $d$ denotes a predetermined positive integer, and $m$ denotes the range of input sequence values plus 1. Setting $d = \sqrt{m}$ minimizes time and space to $\mathcal{O}(n + \sqrt{m})$, resulting in linear time and space $\mathcal{O}(n)$ when $m \leq \mathcal{O}(n^2)$. We provide implementation optimizations for minimizing the time and space complexity, runtime, and number of computations expended by QR Sort, showcasing its adaptability. Our results reveal that QR Sort frequently outperforms established algorithms and serves as a reliable sorting algorithm for input sequences that exhibit large $m$ relative to $n$. Comment: 12 pages, 4 figures, 2 Tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.07526 Zobrazit plný text záznamu View this record from Arxiv