Binary Insertion Sort for Hardware Acceleration: Balancing Flexibility and Resource Efficiency

This paper presents Binary Insertion Sort (BIS), a parallel-friendly sorting algorithm optimized for hardware implementation. By enabling up to k= ⌈ log₂(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.