We develop a new parallel algorithm for sorting which has a time complexity of O(log n) and requires n 2 /log n processors. The algorithm can be readily mapped on 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
['Sujit Dey', 'Pradip K. Srimani']
A new parallel sorting algorithm and its efficient VLSI implementation