A simple architecture for constant time sorting machines
Tsong-Chih Hsu, Sheng‐De Wang · ACM SIGARCH Computer Architecture News · 1995
In this paper, we propose a constant time sorting algorithm on an array composed of comparators and single-pole-double-throw switches, which is far more feasible than other constant time sorting algorithms [21]-[23]. Our results shown that the algorithm uses time T = Θ(1) and area A = O ( N 3 ). This nearly matches the AT 2 = Ω( N 2 log 2 N ) lower bound for sorting in the VLSI model.