Path: utzoo!attcan!ncrcan!becker!censor!comspec!tvcent!lethe!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!rutgers!mit-eddie!uw-beaver!ssc-vax!coy
From: coy@ssc-vax.UUCP (Stephen B Coy)
Newsgroups: comp.misc
Subject: Re: all sorts
Keywords: sorts, shell-metner
Message-ID: <3347@ssc-vax.UUCP>
Date: 6 May 90 22:51:17 GMT
References: <1857@gould.doc.ic.ac.uk} <374@van-bc.UUCP> <5228@helios.TAMU.EDU>
Distribution: comp.graphics
Organization: Boeing Aerospace & Electronics, Seattle WA
Lines: 32

In article <374@van-bc.UUCP} jtc@van-bc.UUCP (J.T. Conklin) writes:
}[Followup-To: comp.misc]
}
}In article <1857@gould.doc.ic.ac.uk> zmacy67@doc.ic.ac.uk (Roger Attrill) writes:
}>  I am currently writing a 3-D solids modeller.  A simple part of this
}>requires the depth sorting of a large number of triangular surfaces. While
}>the quicksort algorithm is ok, I have heard of the Shell-Metzner sort,
}>(actual spelling unknown). I have even spoken to two other people who
}>have heard of it, but I can't find anyone who has GOT it. If any one knows
}>the algorithm, or knows someone who knows someone .....   then I'd be very
}>grateful. Also If anyone knows any other very fast sorting algorithms ( ie 
}>faster than quicksort ) then I'd like to hear from you.
> worst-case running times are bad.

First off, sorry if I've screwed up the attributions.  I've come
across this discussion kind of late.  On to the topic.

One thing to keep in mind is how you are going to manipulate the
images.  If you are going to generate relatively random views of
your object then a quick(er)sort or a shell sort is applicable.  If
you are trying to generate views of the object as you rotate it
slowly an insertion sort will take advantage of the view to view
coherence much better.  As the viewpoint changes, relatively few
polygons will change order from frame to frame.  Also, the ones that
are out of order will still be fairly close to their correct
position.  An insertion sort will be at its best under these
conditions and should be able to outperform the others easily with
complexity approaching O(n).  Another advantage is that its quite
easy to implement.

Stephen Coy
uw-beaver!ssc-vax!coy