Sorting on reconfigurable meshes: An irregular decomposition approach

Most algorithms for reconfigurable meshes (R-meshes) are based on the divid e-and-conquer (DAC) strategy. Although the strategy per se does not require the subproblems to be equal in size, existing DAC algorithms for R-meshes do divide the problem approximately evenly. This paper demonstrates that di viding a problem evenly is not necessarily a good way to decompose a proble m. There are occasions on which an irregular decomposition scheme may be pr eferable. We lake this approach and obtain a new sorting algorithm. Our sor ting algorithm has several strengths: it is simple, scalable, and as broadc ast-efficient as the best known result.