short-paper

Improving counting sort algorithm via data locality

Authors:

Shamsed Mahmud,

Sardar Anisul Haque,

Nazim ChoudhuryAuthors Info & Claims

ACMSE '22: Proceedings of the 2022 ACM Southeast Conference

Pages 211 - 214

https://doi.org/10.1145/3476883.3520203

Published: 04 May 2022 Publication History

Get Access

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.

Digital Library

Google Scholar

[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.

Google Scholar

[3]

Jeff Edmonds. 2008. How to Think About Algorithms. Cambridge University Press.

Google Scholar

[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.

Google Scholar

[5]

Sardar Anisul Haque. 2013. Hardware Acceleration Technologies in Computer Algebra: Challenges and Impact. Ph.D. Dissertation. University of Western Ontario.

Google Scholar

[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.

Google Scholar

[7]

Donald E. Knuth. 1968. The Art of Computer Programming: Fundamental. Algorithms 1 (1968), 187.

Google Scholar

[8]

Donald E. Knuth. 1997. The Art of Computer Programming. Vol. 3. Pearson Education.

Digital Library

Google Scholar

[9]

Donald E. Knuth. 1998. The Art of Computer Programming: Sorting and Searching. Vol. 3. Addison-Wesley, Reading.

Google Scholar

[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.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[12]

Robert Meolic. 2013. Demonstration of Sorting Algorithms on Mobile Platforms. In CSEDU. Aachen, Germany, 136--141.

Google Scholar

[13]

Naila Rahman and Rajeev Raman. 1999. Analysing Cache Effects in Distribution Sorting. In International Workshop on Algorithm Engineering. Springer, London, UK, 183--197.

Google Scholar

[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.

Crossref

Google Scholar

Cited By

View all

Jiang FHu QYang ZLiu JDu J(2025)A neighborhood rough sets-based ensemble method, with application to software fault predictionExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.125919264:COnline publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1016/j.eswa.2024.125919
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
https://doi.org/10.1109/ICNWC60771.2024.10537393

Index Terms

Improving counting sort algorithm via data locality
1. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Divide and conquer
    2. Data structures design and analysis
      1. Sorting and searching

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
Abstract
An 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

ACMSE '22: Proceedings of the 2022 ACM Southeast Conference

April 2022

267 pages

ISBN:9781450386975

DOI:10.1145/3476883

Conference Chair:
Christopher Ogden
Jacksonville State University
,
Program Chair:
Eric Gamess
Jacksonville State University

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Short-paper

Conference

ACM SE '22

Sponsor:

ACM SE '22: 2022 ACM Southeast Conference

April 18 - 20, 2022

Virtual Event

Acceptance Rates

Overall Acceptance Rate 502 of 1,023 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jiang FHu QYang ZLiu JDu J(2025)A neighborhood rough sets-based ensemble method, with application to software fault predictionExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.125919264:COnline publication date: 10-Mar-2025
https://dl.acm.org/doi/10.1016/j.eswa.2024.125919
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
https://doi.org/10.1109/ICNWC60771.2024.10537393

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Bidirectional Conditional Insertion Sort algorithm; An efficient progress on the classical insertion sort

Quadripartite Sort

Implementation of samplesort: A minimal storage tree sort

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations