Faster deterministic sorting through better sampling

✍ Scribed by Jop F. Sibeyn

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 221 KB
• Volume: 290
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00321-3

✦ Synopsis

In this paper, a reÿned 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.