[ont.events] COMPLEXITY SEMINAR at U of T-"Shell Sort: Analysis and Variations" by J. Incerpi, Brown University

voula@utcsri.UUCP (Voula Vanneli) (03/28/85)

                    UNIVERSITY OF TORONTO
              DEPARTMENT OF COMPUTER SCIENCE

COMPLEXITY SEMINAR - Tuesday, April 2, 4 pm, SF 1105

                              Janet Incerpi
                       Brown University, Providence RI.

                     "Shell Sort: Analysis and Variations"

                         Abstract

Shellsort is a well-known sorting method that uses an increment sequence
(h sub i) and works by performing insertion sort of subfiles consisting
of every h sub i element.  Little is understood about the algorithm
aside from the fact that the running time depends on the increment
sequence.  We provide new results on the complexity of Shellshort.
These include a class of logN increment sequences, which both
theoretically and practically are the best known to date.
We also look at variations of Shellsort.  By allowing linear work per
pass, insurance must be given that the file is sorted after 0(logN)
passes.  We describe one such method:  it uses logN passes, has
potential as a practical sorting algorithm, and could possibly lead to
a simple sorting network.