Content area
Abstract
This dissertation examines Shellsort in both an empirical and theoretical manner. Empirical experiments were conducted to find the best increment list to use when Shellsorting a file of a given size. This was only feasible for small file sizes. Other empirical experiments were conducted on increment lists that were simple to generate. The best of these increment lists outperform any previously published increment lists.
Theoretical results arise from using two new solutions to specific instances of the Frobenius problem to generate increment lists. One Frobenius solution gives an increment list that requires no more than $O(n$log$\sp3$n) comparisons to sort a file of size n. The other Frobenius solution gives a family of increment lists that require no more than $O(n\sp{3/2+\epsilon}$) comparisons to sort a file of size n, yet does this using a constant number of increments.
