Sorting on reconfigurable multiple bus machines
R.K. Thiruchelvan, Jerry L. Trahan, Ramachandran Vaidyanathan · 2002
We consider the problem of sorting on an EREW Segmenting Reconfigurable Multiple Bus Machine (S-RMBM). We present optimal algorithms for sorting n keys and n O(loglogn)-bit integers. We also present two S-RMBM algorithms that sort n O(logn)-bit integers in O(lognlog*n) (resp. O(logn)) time with n/lognlog*n (resp. nlog/sup (k/)n/logn) processors. The last two results have not yet been achieved on a CREW PRAM.>