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.