In this paper, a refined deterministic sampling strategy is presented. It allows to improve the performance of deterministic sample-sort algorithms to the point that they can compete with their randomized counterparts. The method is illustrated by a detailed analysis for the cases of sorting on meshes and for sorting in external memory on a single processor machine. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 26]
展开▼
