An O(log n) VLSI implementation of a parallel sorting algorithm
S. Dey, Pradip K. Srimani · 2003
A parallel algorithm for sorting is developed which has a time complexity of O(log n) and requires n/sup 2//log n processors. The algorithm can be readily mapped onto an SIMD mesh-connected array of processors which has all the features of efficient VLSI implementation. The corresponding hardware algorithm maintains the O(log n) execution time and has a low, O(n) interprocessor communication time.>