notice
Doctoral Seminar: Stuart Thiel
Speaker: Stuart Thiel
Supervisor: Dr. G. Butler
Supervisory Committee: Drs. T. Eavis, H. Harutyunyan, F. Khendek
Title: Relaxing the Counting Requirement for Least Significant Digit Radix Sorts
Date: Thursday, April 2, 2015
Time: 11:40 a.m.
Place: EV 3.309
ABSTRACT
Least Significant Digit Radix Sort is a classical distribution sort that makes use of an initial counting pass in its common array-based implementation. In Fast Radix Sort we implement an internal sort that avoids the initial counting step and estimates bin sizes. The dealing pass adapts to errors in estimating bin sizes by using an overflow bin. The experimental results demonstrate a consistent advantage of 4-8% in performance on large data sets across a variety of input distributions.