[ont.events] UW Data Structuring Seminar, Miss Incerpi on "Shellsort: Analysis and Variation"

mwang@watmath.UUCP (mwang) (03/27/85)

DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

DATA STRUCTURING SEMINAR

                    - Monday, April 1, 1985.

Miss  J.  Incerpi  of  Brown  University  will speak on
``Shellsort: Analysis and Variations''.

TIME:         1:30 PM (Please Note)

ROOM:        MC 5158

ABSTRACT

Shellsort  is  a well-known sorting method that uses an
increment sequence
h_i and works by performing insertion sort on subfiles
consisting  of  every  h_ith element.  Little is under-
stood  about the algorithm aside from the fact that the
running time depends on the increment sequence. We pro-
vide new results on the complexity of Shellsort.  These
include  a  class  of  log N increment sequences, which
both  theoretically  and practically are the best known
to  date.   By allowing linear work per pass, insurance
must  be  given that the file is sorted after O( log N)
passes.  We  describe  one  such  method: it uses log N
passes, has potential as a practical sorting algorithm,
and could possibly lead to a simple sorting network.