Lu, Xuanhao, Ahrar, Alireza, Assaad, Maher, Rahimi Azghadi, Mostafa, Genov, Roman, and Amirsoleimani, Amirali (2025) Binary Insertion Sort for Hardware Acceleration: Balancing Flexibility and Resource Efficiency. In: Proceedings of the Midwest Symposium on Circuits and Systems. pp. 488-492. From: MWSCAS 2025: IEEE 68th International Midwest Symposium on Circuits and Systems, 10-13 August 2025, Lansing, MI, USA.

PDF (Published Version) - Published Version Restricted to Repository staff only

 

1

Abstract

This paper presents Binary Insertion Sort (BIS), a parallel-friendly sorting algorithm optimized for hardware implementation. By enabling up to k= ⌈ log2(N-1)⌉ concurrent binary searches, BIS targets a theoretical time complexity of O(N), offering an efficient alternative to comparator-intensive designs. Comparative evaluations against state-of-the-art hard-ware sorting methods, including DL Sort and OWS, show that BIS reduces comparison operations by up to 50% relative to DL Sort while requiring only O(log N) comparators, significantly lowering hardware complexity. Although OWS achieves minimal data movement, its strict dependence on bit-width and input size limits its general applicability. BIS, by contrast, provides a more flexible and scalable architecture, balancing performance, resource efficiency, and adaptability. These qualities position BIS as a strong candidate for integration in real-time and resource-constrained systems.

Actions (Repository Staff Only)

Item Control Page