Cited By
View all- Narayanan YM S(2024)Time and Space Optimization in Linear Time Sorting Using LSORT2024 2nd International Conference on Networking and Communications (ICNWC)10.1109/ICNWC60771.2024.10537393(1-6)Online publication date: 2-Apr-2024
Improving counting sort algorithm via data locality
Pages 211 - 214
Abstract
In this paper, we proposed a cache-friendly hybrid sorting algorithm that combined a non-comparison sorting algorithm (counting sort) with a comparison sort (quick sort) algorithm. The current study leverages the principle of locality to improve the performance of the counting sort algorithm over a large list of integer inputs. We employed a modified version of the original quick sort algorithm to reduce the number of cache misses in counting sort. We also empirically tested the performance of the proposed hybrid algorithm by varying both the range and the quantity of the input values. This hybrid approach not only demonstrated a superior performance over the classic counting sort algorithm but also is capable of facilitating parallelism that was impractical for the classic counting sort algorithm.
References
[1]
Jon L. Bentley and M. Douglas McIlroy. 1993. Engineering a Sort Function. Software: Practice and Experience 23, 11 (1993), 1249--1265.
[2]
Jamison D. Collins and Dean M. Tullsen. 1999. Hardware Identification of Cache Conflict Misses. In MICRO-32. Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture. IEEE, Haifa, Israel, 126--135.
[3]
Jeff Edmonds. 2008. How to Think About Algorithms. Cambridge University Press.
[4]
Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. Cache-oblivious Algorithms. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039). IEEE, New York, USA, 285--297.
[5]
Sardar Anisul Haque. 2013. Hardware Acceleration Technologies in Computer Algebra: Challenges and Impact. Ph.D. Dissertation. University of Western Ontario.
[6]
Wu Jianping, Yutang Ye, Liu Lin, Huang Bingquan, and Guo Tao. 2011. High-speed FPGA-based SOPC Application for Currency Sorting System. In IEEE 2011 10th International Conference on Electronic Measurement & Instruments, Vol. 2. IEEE, Chengdu, China, 85--89.
[7]
Donald E. Knuth. 1968. The Art of Computer Programming: Fundamental. Algorithms 1 (1968), 187.
[8]
Donald E. Knuth. 1997. The Art of Computer Programming. Vol. 3. Pearson Education.
[9]
Donald E. Knuth. 1998. The Art of Computer Programming: Sorting and Searching. Vol. 3. Addison-Wesley, Reading.
[10]
Anthony LaMarca and Richard E. Ladner. 1999. The Influence of Caches on the Performance of Sorting. Journal of Algorithms 31, 1 (1999), 66--104.
[11]
Tom Leighton, Yuan Ma, and C. Greg Plaxton. 1997. Breaking the Θ (n log2 n) Barrier for Sorting with Faults. J. Comput. System Sci. 54, 2 (1997), 265--304.
[12]
Robert Meolic. 2013. Demonstration of Sorting Algorithms on Mobile Platforms. In CSEDU. Aachen, Germany, 136--141.
[13]
Naila Rahman and Rajeev Raman. 1999. Analysing Cache Effects in Distribution Sorting. In International Workshop on Algorithm Engineering. Springer, London, UK, 183--197.
[14]
Ran Zhang, Xue Wei, and Takahiro Watanabe. 2013. A Sorting-based IO Connection Assignment for Flip-chip Designs. In 2013 IEEE 10th International Conference on ASIC. IEEE, Shenzhen, China, 1--4.
Index Terms
- Improving counting sort algorithm via data locality
Recommendations
Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort
In this paper, we proposed a new efficient sorting algorithm based on insertion sort concept. The proposed algorithm is called Bidirectional Conditional Insertion Sort (BCIS). It is in-place sorting algorithm and it has remarkably efficient average case ...
Quadripartite Sort
This paper presents an efficient and practical sorting algorithm, called Quadripartite Sort. It lies between MergeSort and QuickSort. This algorithm sortsnelements using bounded workspace andnlogn+1.75ncomparisons in the worst case. By empirical testing,...
Implementation of samplesort: A minimal storage tree sort
AbstractAn implementation of samplesort, a generalization of minimal-storage tree-sorting, is presented as an algorithm which is relatively insensitive to possible non-random permutations of the elements to be sorted. A brief analytical discussion and the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2022
267 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 May 2022
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
ACM SE '22
Sponsor:
Acceptance Rates
Overall Acceptance Rate 502 of 1,023 submissions, 49%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 170Total Downloads
- Downloads (Last 12 months)43
- Downloads (Last 6 weeks)10
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
Cited By
View all- Narayanan YM S(2024)Time and Space Optimization in Linear Time Sorting Using LSORT2024 2nd International Conference on Networking and Communications (ICNWC)10.1109/ICNWC60771.2024.10537393(1-6)Online publication date: 2-Apr-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in