Sorting on reconfigurable multiple bus machines

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^(k/)n logn) processors. The last two results have not yet been achieved on a CREW PRAM