QR Sort: A New Non-Comparative Integer-Based Sorting Algorithm

In this paper, we introduce a new stable, non-comparative integer-based sorting algorithm with an attainable linear time complexity, O(n). This approach utilizes the Quotient Remainder Theorem in conjunction with Counting Sort subroutines. This algorithm divides each input array element by a selected positive integer divisor, d, to generate representative remainder and quotient keys. We perform Counting Sort on the remain-der keys followed by the quotient keys. This method yields a time and space complexity of O(n + d + k/d), where k represents the difference between maximum and minimum array values. If we set the divisor, d, equal to the length of the input array, n, the complexity simplifies to O(n + k/n). As the length of the input array increases and the value of k remains constant, the time complexity converges to O(n). Our results indicate that our algorithm outperforms established integer-based sorting algorithms such as Counting Sort and Least Significant DigitRadix Sort with large input arrays. We present our methodology and comprehensive discussion of our results in the main body of the paper.