| A Practical Algorithm for Integer Sorting on a Mesh-Connected Computer (Preliminary Version) (2006) | |||||||||||
Abstract | |||||||||||
| This paper presents count-sort, a parallel algorithm for mesh- connected computers to sort integers where the range of inputs is known. A straightforward counting technique that has not been implemented previously in parallel sorting algorithms is presented. On a mesh-connected computer with square root N x square root N processors we are able to sort N integers in the range 1... square root N in time c square root N where c is very small. For practical values of N, the algorithm is extremely fast. Further, it is possible to expand the range by a factor k to 1 ... k square root N so that the slowdown is less than k. We produce an implementation of count-sort on the SIMD MasPar MP-1 with 8192 processors that sorts 8-bit integers significantly faster than the manufacturer's current library routine for sorting 8-bit integers. | |||||||||||
Publication details | |||||||||||
| |||||||||||