Path: utzoo!censor!comspec!humvax!becker!lethe!torsqnt!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!helios!gordon
From: gordon@cs.tamu.edu (Dan Gordon)
Newsgroups: comp.misc
Subject: Re: all sorts
Keywords: sorts, shell-metner
Message-ID: <5228@helios.TAMU.EDU>
Date: 5 May 90 15:13:22 GMT
References: <1857@gould.doc.ic.ac.uk} <374@van-bc.UUCP>
Sender: usenet@helios.TAMU.EDU
Distribution: comp.graphics
Organization: Computer Science Department, Texas A&M University
Lines: 43

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.
}
}You really need to grab an elementary algorithms text before you start
}evaluating the performance of sorting algorithms.  I suggest taking a 
}look at Knuth's Sorting and Searching.
}
}That said, every algorithm has its strengths and weaknesses.  The data
}that you are working with will play a large part of which algoritm you
}choose.
}
}For example, the ubiquous bubblesort.  It is small, easy to implement,
 
}Quicksort is is generally quite fast O(n log n), but its worst case

}The Shell sort tends to fall between the fast algorithms like

		--- stuff deleted ---

If you want to do depth sorting, your best bet is to use bucket sort. 
For every integral value of z between ZMIN and ZMAX, you maintain a 
sorted linked list of all the points whose integral value of z is equal
to the bucket number (see any good book on data structures and/or design
& analysis of algorithms). After all the points have been inserted into
the buckets, you can traverse all the linked lists and copy the points
into an array. Alternatively, by maintaining also a pointer to the end
of each list, you can (at the end) efficiently link all the lists 
together into one sorted linked list.

Let us all know which method works best in your situation. It has been
demonstrated that for various problems in computational geometry, 
bucketing techniques work best in practice, even though their theoretical
worst-case running times are bad.