i-manager Publications

A Comparitive Study of Sorting Architectures with a Proposed Hybrid Approach

Chrysolite Joy S.*, Santhi C.**

*-** Department of Electronics and Communication Engineering, Government College of Technology, Coimbatore, Tamil Nadu, India.

Periodicity:January - June'2025

Abstract

Sorting plays a crucial role in various applications, including high-performance computing, image processing, and network systems. Traditional sorting algorithms are efficient in software but can be a computational bottleneck in hardware implementations. This paper laid out various sorting architectures like Odd-Even Sort, Bitonic Sort, and Odd- Even Merge Sort with a detailed overview of their area, power and performance metrics. A Scalable and Hardware- Efficient Bidirectional Hybrid Sorting of Odd-Even Merge Sort and Bidirectional Insertion Sort. These designs were created using Verilog HDL simulated in Cadence Incisive and synthesized in Genus. Proposed architecture reduces area, power, and delay by up to 1.63%, 3.68%, and 16.93%, respectively, over existing design. The comparison made in the analysis of these data indicates the effectiveness of the proposed methodology in terms of resource allocation as well as preservation of the high efficiency of the sorting operation, indicating its applicability in such systems where resource allocation is inadequate in the comparison mode applied.

Keywords

Bitonic Sort, HDL, Hybrid sorting, Pipelined Architecture, Verilog.

How to Cite this Article?

Joy, S. C., and Santhi, C. (2025). A Comparitive Study of Sorting Architectures with a Proposed Hybrid Approach. i-manager’s Journal on Circuits and Systems, 13(1), 6-17.

References

[1]. Abdel-Hafeez, S., & Gordon-Ross, A. (2017). An efficient O ($ N $) comparison-Free sorting algorithm. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 25(6), 1930-1942.

[2]. Batcher, K. E. (1968). Sorting networks and their applications. In Proceedings of the May 2, 1968, Spring Joint Computer Conference (pp. 307-314).

[3]. Bentley, J. L., & Sedgewick, R. (1997). Fast algorithms for sorting and searching strings. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 360-369).

[4]. Busse, L. M., Chehreghani, M. H., & Buhmann, J. M. (2012). The information content in sorting algorithms. In 2012 IEEE International Symposium on Information Theory Proceedings (pp. 2746-2750). IEEE.

[5]. Canaan, C., Garai, M. S., & Daya, M. (2011). Popular sorting algorithms. World Applied Programming, 1(1), 42- 50.

[6]. Chen, R., Siriyal, S., & Prasanna, V. (2015). Energy and memory efficient mapping of bitonic sorting on FPGA. In Proceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (pp. 240-249).

[7]. Chen, S., Zhang, T., & Xin, Y. (2007). Relaxed $ K $-best MIMO signal detector design and VLSI implementation. IEEE Transactions on Very Large Scale Integration (VLSI) systems, 15(3), 328-337.

[8]. Chen, W. T., Chen, R. D., Chen, P. Y., & Hsiao, Y. C. (2021). A high-performance bidirectional architecture for the quasi-comparison-free sorting algorithm. IEEE Transactions on Circuits and Systems I: Regular Papers, 68(4), 1493-1506.

[9]. Chen, W., Li, W., & Yu, F. (2019). A hybrid pipelined architecture for high performance top-K sorting on FPGA. IEEE Transactions on Circuits and Systems II: Express Briefs, 67(8), 1449-1453.

[10]. Chen, Y. R., Ho, C. C., Chen, W. T., & Chen, P. Y.(2023). A low-cost pipelined architecture based on a hybrid sorting algorithm. IEEE Transactions on Circuits and Systems I: Regular Papers, 71(2), 717-730.

[11]. Gabiger-Rose, A., Kube, M., Weigel, R., & Rose, R. (2013). An FPGA-based fully synchronized design of a bilateral filter for real-time image denoising. IEEE Transactions on Industrial Electronics, 61(8), 4093-4104.

[12]. Han, Y. (2002). Deterministic sorting in O (n log log n) time and linear space. In Proceedings of The Thirty-Fourth Annual ACM Symposium on Theory of Computing (pp. 602-608).

[13]. Knuth, D. E. (1997). The Art of Computer Programming (Vol. 3). Pearson Education.

[14]. Kumari, S., & Singh, D. P. (2014). A parallel selection sorting algorithm on GPUs using binary search. In 2014 International Conference on Advances in Engineering & Technology Research (ICAETR-2014) (pp. 1-6). IEEE.

[15]. Leighton, T., Ma, Y., & Plaxton, C. G. (1997). Breaking theΘ (n log2 n) barrier for sorting with faults. Journal of Computer and System Sciences, 54(2), 265-304.

[16]. Leu, F. C., Tsai, Y. T., & Tang, C. Y. (2000). An efficient external sorting algorithm. Information Processing Letters, 75(4), 159-163.

[17]. Njejimana, L., Tétrault, M. A., Arpin, L., Burghgraeve, A., Maillé, P., Lavoie, J. C., & Fontaine, R. (2013). Design of a real-time FPGA-based data acquisition architecture for the LabPET II: An APD-based scanner dedicated to small animal PET imaging. IEEE Transactions on Nuclear Science, 60(5), 3633-3638.

[18]. Ray, S. S., & Ghosh, S. (2022). K-degree parallel comparison-free hardware sorter for complete sorting. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(5), 1438-1449.

[19]. Ray, S. S., Adak, D., & Ghosh, S. (2021). Worst case O(N) comparison-free hardware sorting engine. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 41(10), 3332-3345.

[20]. Sareen, P. (2013). Comparison of sorting algorithms (on the basis of average case). International Journal of Advanced Research in Computer Science and Software Engineering, 3(3), 522-532.

[21]. Shabany, M., & Gulak, G. (2012). P.: A 675 mbps, 4x4 64-QAM K-Best MIMO detector in 0.13 um CMOS. IEEE Transactions on Very Large Scale Integration (VLSI) systems, 20(1), 1063-8210.

[22]. Xiao, L., Zhang, X., & Kubricht, S. A. (2000). Improving memory performance of sorting algorithms. Journal of Experimental Algorithmics (JEA), 5, 3-es.

[23]. Zhang, Y., & Zheng, S. J. (1994). A simple and efficient VLSI sorting architecture. In Proceedings of 1994 37th Midwest Symposium on Circuits and Systems, 1, 70-73. IEEE.

	North Americas,UK, Middle East,Europe		India	Rest of world
	USD	EUR	INR	USD-ROW
Pdf	35	35	200	20
Online	15	15	200	15
Pdf & Online	35	35	400	25

A Comparitive Study of Sorting Architectures with a Proposed Hybrid Approach

Abstract

Keywords

How to Cite this Article?

References

If you have access to this article please login to view the article or kindly login to purchase the article

Purchase Instant Access

Options for accessing this content: