Load balancing, selection sorting on the hypercube
C. Gregory Plaxton · 1989
This paper presents novel load balancing, selection and sorting algorithms for the hypercube with l-port communication.The main result is an algorithm for sorting n values on p processors, $taooth$ort, that runs asymptotically faster (in the worst case) than any previously known algorithm over a wide range of the ratio nip.The load balancing and selection algorithms upon which StmothSort is based are expected to be of independent interest.Although the analysis of our algorithms is llmited to obtaining asymptotic bounds, the constant factors being ignored axe quite tmaalL