🚀 go-pugleaf

 scd@cs.brown.edu (Steven C. Dollins) writes:
>
>The bubble sort takes, in the asymptotic limit, 1/2 N^2 time, which is
>nowhere NEAR N!.  Where on earth did you get that idea?
>
>Quick sort is O(n log n) on average, O(n^2) in the worst case.  With a
>good randomized quick sort, the worst case will be extremely unlikely.

A point about quicksort, as implemented in the C libraries: you can get
about 4x speedup by hand-coding assembler for the routine.  Even 
a direct C implementation runs faster.
If you are sorting 6 or less items, I'd still use something like an
insert or bubble sort, because the overhead is less (no recursion).
It turns out to be faster, especially when coded in assembler.  For
10 or more, it's worth using the quicksort.  For 4 or 5 items, I 
often hard-code the tests and swaps of the sort as this is very
fast-- no indexing or looping (great for drawing polygons).


--------------------------------------------------------------------------
| My life is Hardware,                    |         Dave Stampe          | 
| my destiny is Software,                 | dstampe@psych.toronto.edu    |
| my CPU is Wetware...                    | dstampe@sunee.uwaterloo.ca   | 
| Am I a techno-psychologist, or just an engineer dabbling in psychology?|
---------------------------------------------------------------------------