Guidesort: Simpler Optimal Deterministic Sorting for the Parallel Disk Model

Torben Hagerup

A new algorithm, Guidesort, for sorting in the uniprocessor variant of the parallel disk model (PDM) of Vitter and Shriver is presented. The algorithm is deterministic and executes a number of (parallel) I/O operations that comes within a constant factor $C$ of the optimum. The algorithm and its analysis are simpler than those proposed in previous work, and the achievable constant factor $C$ of essentially 3 appears to be smaller than for all other known deterministic algorithms, at least for plausible parameter values.

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment