Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!apple!ames!eos!shelby!neon!rokicki
From: rokicki@Neon.Stanford.EDU (Tomas G. Rokicki)
Newsgroups: comp.graphics
Subject: Sorting
Message-ID: <1990May4.195435.25668@Neon.Stanford.EDU>
Date: 4 May 90 19:54:35 GMT
Organization: Computer Science Department, Stanford University
Lines: 13

> Quicksort is is generally quite fast O(n log n), but its worst case
> behavior (a pre-sorted list) is O(n^2).  If your list tends to stay
> sorted, a you might choose other O(n log n) algorithms like heapsort
> or mergesort.

Depends on how you implement quicksort; no good implementation takes
n^2 on a sorted list.  Median of three partitioning works well.

For an excellent simple sort, see Harrison and Steele (I forgot the
page number); it's a line more than bubble sort, but much faster.
(It's just got the Shell sort loop . . .)

-tom